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

Візуалізація двійкового пошуку

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

Трудомісткість алгоритму $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 // не знайдено
}

Версія без перевірки на рівність

Попередні версії на кожному кроку перевіряють поточний елемент на рівність шуканому. Це може бути досить повільним, якщо порівняння не є швидкими. Також коли в масиві декілька рівних елементів, то попередні алгоритми знаходять будь-який з них. Можна змінити алгоритм, щоб не використовувати порівняння:

BinarySearchFistPosition(A[0, N-1], value) {
  low = -1
  high = N
  while (high - low > 1) {
     mid = (high + low) / 2
     if (A[mid] >= value)
         high = mid
     else
         low = mid
  }
   // Тепер в high знаходиться індекс першого елемента, такого що A[high] >= value.
   // Якщо це необхідно можна перевірити чи він рівний value
   if (A[high] > value)
      // не знайдено, high = 0 чи A[high - 1] < value, A[high] > value
   else
      // Знайдено
   return high
}

BinarySearchLastPosition(A[0, N-1], value) {
    low = -1
    high = N
    while (high - low > 1) {
        mid = (high + low) / 2
        if (A[mid] <= value)
             low = mid
        else
             high = mid
    }
    // Зараз у high знаходиться індекс першого елемента такого, що A[high] > value, а в A[low] - останнього елемента такого, що A[low] <= value
    return low
}

В сумі ці дві версії можна використовувати, наприклад, щоб знайти скільки елементів масиву рівні даному.

Цікаві дані

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

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

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

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

Помилки в реалізації

Нескінченний цикл

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

right = mid;

та

else left = mid;

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

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

Переповнення

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

int mid = (low + high) / 2;

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

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

чи

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

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

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

Література

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

Див. також

• Список алгоритмів
• Лінійний пошук
• Метод золотого перетину