Целочисленный двоичный поиск — различия между версиями
Alex700 (обсуждение | вклад) |
|||
| Строка 34: | Строка 34: | ||
== Код == | == Код == | ||
| − | + | binSearch('''Object[]''' a, '''Object''' key) <font color="green">// l, r - левая и правая границы</font> | |
| − | + | '''int''' l = 0 | |
| − | + | '''int''' r = len(a) + 1 | |
| − | + | '''while''' l < r - 1 <font color="green">// запускаем цикл</font> | |
| − | + | m = (l + r) / 2 <font color="green">// m - середина области поиска</font> | |
| − | + | '''if''' a[m] < key | |
| − | + | l = m | |
| − | </ | + | '''else''' |
| + | r = m <font color="green">// сужение границ</font> | ||
| + | '''return''' r | ||
| + | |||
| + | |||
В случае правостороннего поиска изменится знак сравнения при сужении границ на (<tex>a[m] \leqslant k</tex>). | В случае правостороннего поиска изменится знак сравнения при сужении границ на (<tex>a[m] \leqslant k</tex>). | ||
Версия 21:57, 29 мая 2014
| Определение: |
| Целочисленный двоичный поиск (бин. поиск) (от англ. Binary Search) — алгоритм поиска объекта по заданному признаку во множестве объектов, упорядоченных по тому же самому признаку. |
Содержание
Формулировка задачи
Пусть нам дан упорядоченный массив, состоящий только из целочисленных элементов. Нам надо найти в нём индекс, по которому находится искомый элемент, или же мы можем находить интервалы вхождения искомого элемента. Для этой задачи мы и можем использовать двоичный поиск.
Принцип работы
Двоичный поиск заключается в том, что на каждом шаге множество объектов делится на две части и в работе остаётся та часть множества, где находится искомый объект. Или же, в зависимости от постановки задачи, мы можем остановить процесс, когда мы получим первый или же последний индекс вхождения элемента. Последнее условие — это левосторонний/правосторонний двоичный поиск.
Правосторонний/левосторонний целочисленный двоичный поиск
Когда мы ищем правосторонним бинарным поиском, то он возвращает индекс самого правого вхождения заданного значения .
Когда же поиск левосторонний, возвращается индекс самого левого вхождения заданного значения .
Это разделение помогает находить количество подряд идущих равных значений.
Например:
Задан отсортированный массив
Правосторонний поиск двойки выдаст в результате , в то время как левосторонний выдаст .
От сюда следует, что количество подряд идущих двоек равно длине отрезка , то есть .
Если искомого элемента в массиве нет, то правосторонний поиск выдаст минимальный элемент, больший искомого, а левосторонний наоборот, максимальный элемент, меньший искомого.
Алгоритм двоичного поиска
Идея поиска заключается в том, чтобы брать элемент посередине, между границами, и сравнивать его с искомым. В случае равенства возвращать его, а если искомое больше(в случае правостороннего — не меньше), чем элемент сравнения, то сужаем область поиска так, чтобы новая левая граница была равна индексу середины предыдущей области. В противном случае присваиваем это значение правой границе. Проделываем эту процедуру до тех пор, пока правая граница больше левой более чем на , или же пока мы не найдём искомый индекс.
Код
binSearch(Object[] a, Object key) // l, r - левая и правая границы
int l = 0
int r = len(a) + 1
while l < r - 1 // запускаем цикл
m = (l + r) / 2 // m - середина области поиска
if a[m] < key
l = m
else
r = m // сужение границ
return r
В случае правостороннего поиска изменится знак сравнения при сужении границ на ().
Инвариант цикла: пусть левый индекс меньше или равен искомого элемента, а правый — строго больше, тогда если , то понятно, что — самое правое вхождение (так как следующее уже больше).
См. также
Источники
- Д. Кнут - Искусство программирования (Том 3, 2-е издание)
