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

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

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

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

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

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

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

Двійковий пошук суттєво швидший за лінійний, відносно простий в реалізації і загальновживаний. Проте, в реальних програмах трапляються випадки використання лінійного пошуку, що мають наслідком суттєві проблеми зі швидкодією. Так, в серйозній науковій публікації[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.

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