Двійковий пошук

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Двійкóвий пóшук — алгоритм знаходження заданого значення у впорядкованому масиві, який полягає у порівнянні серединного елемента масиву з шуканим значенням, і повторенням алгоритму для тієї або іншої половини (див. двійкове дерево пошуку), залежно від результату порівняння.

Трудомісткість алгоритму 1 + \log_2 n, де n — кількість елементів у масиві.

Алгоритм[ред.ред. код]

Рекурсивна версія[ред.ред. код]

Одним із варіантів реалізації алгоритму є рекурсивна функція, що отримує масив, шукане значення та початковий і кінцевий індекси елементів в масиві.

BinarySearch(A[0..N-1], value, low, high) {
     if (high < low)
         return -1 // не знайдено
     mid = (low + high) / 2
     if (A[mid] > value)
         return BinarySearch(A, value, low, mid-1)
     else if (A[mid] < value)
         return BinarySearch(A, value, mid+1, high)
     else
         return mid // знайдено
   }

Ітеративна версія[ред.ред. код]

Наведений вище алгоритм можна перетворити на ітеративний:

BinarySearch(A[0..N-1], value) {
  low = 0
  high = N - 1
  while (low <= high) {
    mid = (low + high) / 2
    if (A[mid] > value)
      high = mid - 1
    else
      if (A[mid] < value)
        low = mid + 1
      else
        return mid // знайдено
  }
  return -1 // не знайдено
}

Цікаві дані[ред.ред. код]

Масове використання лінійного пошуку[ред.ред. код]

Двійковий пошук суттєво швидший за лінійний, відносно простий в реалізації і загальновживаний. Проте, в реальних програмах трапляються випадки використання лінійного пошуку, що мають наслідком суттєві проблеми зі швидкодією. Так, в серйозній науковій публікації[1] є такий шматок:

Ми мали програму, яка робила лінійний пошук у дуже великому масиві майже 100 раз на секунду. … Ми відстежили проблему до лінійного пошуку, замінили його на двійковий, і проблема зникла

який Джон Бентлі (англ. Jon Bentley) у книзі «Перлини програмування»[2] назвав анекдотом і повідомив, що бачив цю саму історію у багатьох системах. Опублікована на сайті Borland стаття описує проблеми швидкодії, викликані реалізацією певних процедур роботи з базами даних у VCL, які по суті зводяться до використання лінійного пошуку замість двійкового (невикористання індексу таблиці).

Помилки в реалізації[ред.ред. код]

Нескінченний цикл[ред.ред. код]

В тій же книзі Джон Бентлі використовує двійковий пошук як приклад упродовж розділу присвяченого тестуванню та відлагодженню. Він наводить типову невірну реалізацію двійкового пошуку, поширену, за його словами, серед професійних програмістів. Невірний код відрізняється від наведеного далі прикладу рядками

right = mid;

та

else left = mid;

Такий код призводить до нескінченного циклу для багатьох значень шуканого елемента, наприклад, при спробі знайти найбільший елемент масиву.

За спогадами Джошуа Блоха (англ. Joshua Bloch), йому запала в пам'ять лекція з курсу алгоритмів в Університеті Карнегі Мелон, на якій Джон Бентлі попросив майбутніх кандидатів наук написати двійковий пошук, і розібрав невірний варіант, яких було більшість.

Переповнення[ред.ред. код]

Сам Джошуа є автором реалізації бібліотечної функції двійкового пошуку у Java від Sun. У 2006 році він був шокований ще раз, коли довідався, що ретельно розібрана у Бентлі реалізація, та його власна, яка 9 років знаходилась у бібліотеці Java, містить ще одну помилку[3]. Одна програма, що обробляла великий набір даних, падала через наступний рядок у реалізації:

int mid = (low + high) / 2;

Причиною було те, що low і high були великими, і їх сума викликала переповнення типу int, приводячи до від'ємного значення mid. Таким чином, для обробки великих масивів необхідно писати в реалізації на Java:

int mid = low + ((high - low) / 2);

чи

int mid = (low + high) >>> 1;

Допис Блоха також вразив творця Mono Мігеля де Іказу[4], але менше вразив розробника Gnome Мортена Веліндера, який також відмітив інші проблеми з арифетикою цього алгоритму[5].

Після допису Блоха ця помилка була виправлена у Mono[6], помилка досі присутня у функції bsearch реалізації GNU C Library (glibc) бібліотеки мови Сі [7].

Посилання[ред.ред. код]

Література[ред.ред. код]

  • Вірт Н. (1985), Алгоритми та структури даних, розділ 1.9.2.

Див. також[ред.ред. код]