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

[[File:Binary-search-work.gif|thumb|right|Візуалізація двійкового пошуку]]

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

Трудомісткість алгоритму <math>1 + \log_2 n</math>, де ''n''&nbsp;— кількість елементів у масиві.

== Алгоритм ==

=== Рекурсивна версія ===

Одним із варіантів реалізації алгоритму є [[рекурсія|рекурсивна]] функція, що отримує масив, шукане значення та початковий і кінцевий індекси елементів в масиві.
<pre>
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 // знайдено
   }
</pre>

=== Ітеративна версія ===

Наведений вище алгоритм можна перетворити на ітеративний:
<pre>
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 // не знайдено
}
</pre>

=== Версія без перевірки на рівність === 
Попередні версії на кожному кроку перевіряють поточний елемент на рівність шуканому. Це може бути досить повільним, якщо порівняння не є швидкими. Також коли в масиві декілька рівних елементів, то попередні алгоритми знаходять будь-який з них. Можна змінити алгоритм, щоб не використовувати порівняння:
<pre>
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
}
</pre>
В сумі ці дві версії можна використовувати, наприклад, щоб знайти скільки елементів масиву рівні даному.

== Цікаві дані ==

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

Двійковий пошук суттєво швидший за [[лінійний пошук|лінійний]], відносно простий в реалізації і загальновживаний. Проте, в реальних програмах трапляються випадки використання лінійного пошуку, що мають наслідком суттєві проблеми зі швидкодією. Так, в серйозній науковій публікації<ref>[http://portal.acm.org/citation.cfm?coll=GUIDE&dl=GUIDE&id=358192 Communications of the ACM "TWA Reservation system"]</ref> є такий шматок:

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

який [[Джон Бентлі]] ({{lang-en|Jon Bentley}}) у книзі «Перлини програмування»<ref>{{cite book
| last = Bentley
| first = Jon
| authorlink = Jon Bentley
| title = Programming Pearls
| edition = 2nd edition
| pages = p34
| publisher = [[Addison-Wesley]] 
| year = 2000
| origyear = 1986
| isbn = 0201657880 }}</ref> назвав [[анекдот]]ом і повідомив, що бачив цю саму історію у багатьох системах. Опублікована на сайті [[Borland]] [https://web.archive.org/web/20060518075829/http://thecoadletter.com/article/0,1410,32065,00.html стаття] описує проблеми швидкодії, викликані реалізацією певних процедур роботи з [[база даних|базами даних]] у [[Visual Component Library|VCL]], які по суті зводяться до використання лінійного пошуку замість двійкового (невикористання індексу таблиці).

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

 right = mid;

та

 else left = mid;

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

За [http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html спогадами] {{Webarchive|url=https://web.archive.org/web/20160401140544/http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html |date=1 квітня 2016 }} [[Джошуа Блох]]а ({{lang-en|Joshua Bloch}}), йому запала в пам'ять лекція з курсу алгоритмів в [[Університет Карнегі-Меллон|Університеті Карнегі Мелон]], на якій Джон Бентлі попросив майбутніх кандидатів наук написати двійковий пошук, і розібрав невірний варіант, яких було більшість.

==== Переповнення ====
Сам Джошуа є автором реалізації бібліотечної функції двійкового пошуку у [[Java]] від [[Sun Microsystems|Sun]]. У [[2006]] році він був шокований ще раз, коли довідався, що ретельно розібрана у Бентлі реалізація, та його власна, яка 9 років знаходилась у бібліотеці Java, містить ще одну помилку<ref>{{Cite web |url=http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=5045582 |title=Архівована копія |accessdate=3 квітня 2009 |archive-date=14 вересня 2007 |archive-url=https://web.archive.org/web/20070914102845/http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=5045582 }}</ref>. Одна програма, що обробляла великий набір даних, [[зависання|падала]] через наступний рядок у реалізації:
<syntaxhighlight lang="java">
int mid = (low + high) / 2;
</syntaxhighlight>

Причиною було те, що low і high були великими, і їх сума викликала [[програмне переповнення]] типу int, приводячи до від'ємного значення mid.
Таким чином, для обробки великих масивів необхідно писати в реалізації на Java:
<syntaxhighlight lang="java">
int mid = low + ((high - low) / 2);
</syntaxhighlight>
чи
<syntaxhighlight lang="java">
int mid = (low + high) >>> 1;
</syntaxhighlight>

Допис Блоха також вразив творця [[Mono]] Мігеля де Іказу<ref>{{Cite web |url=http://tirania.org/blog/archive/2006/Jun-03-1.html |title=http://tirania.org/blog/archive/2006/Jun-03-1.html |accessdate=8 жовтня 2010 |archive-date=28 листопада 2010 |archive-url=https://web.archive.org/web/20101128202422/http://tirania.org/blog/archive/2006/Jun-03-1.html }}</ref>, але менше вразив розробника [[Gnome]] Мортена Веліндера, який також відмітив інші проблеми з арифметикою цього алгоритму<ref>{{Cite web |url=http://blogs.gnome.org/mortenw/2006/06/05/binary-search/ |title=Morten Welinder: Binary Search |accessdate=8 жовтня 2010 |archive-date=17 грудня 2009 |archive-url=https://web.archive.org/web/20091217100633/http://blogs.gnome.org/mortenw/2006/06/05/binary-search/ }}</ref>.

Після допису Блоха ця помилка була виправлена у [[Mono]]<ref>[http://www.mail-archive.com/mono-devel-list@lists.ximian.com/msg08029.html Mono-dev: Patch for fixing binary search]</ref>, помилка досі присутня у функції bsearch реалізації GNU C Library ([[glibc]]) бібліотеки мови [[Сі (мова програмування)|Сі]] <ref>[http://sourceware.org/git/?p=glibc.git;a=blob;f=stdlib/bsearch.c;hb=bcaad6ee587ce17cc7152879d835e8b643a75bff idx = (l + u) / 2;]{{Недоступне посилання|date=липень 2019 |bot=InternetArchiveBot }}</ref>.

== Див. також ==
* [[Список алгоритмів]]
* [[Лінійний пошук]]
* [[Метод золотого перетину]]

== Посилання ==
{{reflist}}

== Джерела ==
* {{Wirth.Algorithms and Data Structures}}
* {{TAOCP.v3}}
* {{CLRS}}

{{Algorithms-stub}}

[[Категорія:Алгоритми пошуку]]
[[Категорія:Статті з прикладами коду мовою Java]]
[[Категорія:2 (число)]]