Просмотр исходного текста страницы Целочисленный двоичный поиск

{{Определение
|definition=
'''Целочисленный двоичный поиск (бин. поиск) <i>(от англ. Binary Search)</i>'''  {{---}} алгоритм поиска объекта по заданному признаку во множестве объектов, упорядоченных по тому же самому признаку. 
}}

== Формулировка задачи ==
Пусть нам дан упорядоченный массив, состоящий только из целочисленных элементов. Нам надо найти в нём индекс, по которому находится искомый элемент, или же мы можем находить интервалы вхождения искомого элемента. Для этой задачи мы и можем использовать двоичный поиск.

==Принцип работы==
Двоичный поиск заключается в том, что на каждом шаге множество объектов делится на две части и в работе остаётся та часть множества, где находится искомый объект. Или же, в зависимости от постановки задачи, мы можем остановить процесс, когда мы получим первый или же последний индекс вхождения элемента. Последнее условие {{---}} это левосторонний/правосторонний двоичный поиск.

== Правосторонний/левосторонний целочисленный двоичный поиск ==
Когда мы ищем правосторонним бинарным поиском, то он возвращает индекс самого правого вхождения заданного значения <tex> x </tex> .

Когда же поиск левосторонний, возвращается индекс самого левого вхождения заданного значения <tex> x </tex> .

Это разделение помогает находить количество подряд идущих равных значений.

<b><i>Например:</i></b> <br>
Задан отсортированный массив <tex>[1, 2, 2, 2, 2, 3, 5, 8, 9, 11]</tex>

Правосторонний поиск двойки выдаст в результате <tex>5</tex>, в то время как левосторонний выдаст <tex>2</tex>.

От сюда следует, что количество подряд идущих двоек равно длине отрезка <tex>[2;5]</tex>, то есть <tex>4</tex>.

Если искомого элемента в массиве нет, то правосторонний поиск выдаст минимальный элемент, больший искомого, а левосторонний наоборот, максимальный элемент, меньший искомого.

== Алгоритм двоичного поиска == 
[[Файл:shcemebinsearch.png|350px|thumb|right|Схема бин. поиска]]
Идея поиска заключается в том, чтобы брать элемент посередине, между границами, и сравнивать его с искомым.
В случае равенства возвращать его, а если искомое больше(в случае правостороннего {{---}} не меньше), чем элемент сравнения,
то сужаем область поиска так, чтобы новая левая граница была равна индексу середины предыдущей области. В противном случае присваиваем это значение правой границе. Проделываем эту процедуру до тех пор, пока правая граница больше левой более чем на <tex>1</tex>, или же пока мы не найдём искомый индекс.

== Код ==
<pre>binSearch(l, r)                     // l, r - левая и правая границы
    while l < r - 1                 // запускаем цикл
        m = (l + r) / 2;            // m - середина области поиска
        if a[m] < k
            l = m; 
        else 
            r = m;                  // сужение границ
</pre>	
В случае правостороннего поиска изменится знак сравнения при сужении границ на (<tex>a[m] \leqslant k</tex>).

Инвариант цикла: пусть левый индекс меньше или равен искомого элемента, а правый {{---}} строго больше, тогда если <tex>l = r - 1</tex>, то понятно, что <tex>l</tex> {{---}} самое правое вхождение (так как следующее уже больше).

== См. также ==
* [[Вещественный_двоичный_поиск|Вещественный двоичный поиск]]
* [[Троичный_поиск|Троичный поиск]]
* [[Поиск_с_помощью_золотого_сечения|Поиск с помощью золотого сечения]]
* [[Интерполяционный_поиск|Интерполяционный поиск]]

== Источники ==

*Д. Кнут - Искусство программирования (Том 3, 2-е издание)

==Ссылки==
[http://ru.wikipedia.org/wiki/%D0%94%D0%B2%D0%BE%D0%B8%D1%87%D0%BD%D1%8B%D0%B9_%D0%BF%D0%BE%D0%B8%D1%81%D0%BA Википедия - двоичный поиск]


[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Алгоритмы поиска]]