Пояснено алгоритм пошуку переходів

Перейти пошук

Пошук при переході знаходить елемент у відсортованому масиві, перестрибуючи k itens, а потім перевіряє, чи знаходиться потрібний елемент між попереднім переходом і поточним переходом.

Складність Найгірший випадок

O (√N)

Як це працює

  1. Визначте значення k, кількість стрибка: Оптимальний розмір стрибка √N, де N - довжина масиву
  2. Перейти до масиву k-by-k, шукаючи за умовою Array[i] < valueWanted < Array[i+k]
  3. Зробіть лінійний пошук між Array[i]іArray[i + k]
Перехідний пошук 1

Код

Щоб переглянути приклади реалізації коду цього методу, перейдіть за цим посиланням нижче:

Швидкий пошук - OpenGenus / cosmos

Кредити

Зображення масиву логіки