Двоичный поиск
Двоичный (бинарный) поиск (также известен как метод деления пополам или дихотомия) — классический алгоритм поиска элемента в отсортированном массиве (векторе), использующий дробление массива на половины. Используется в информатике, вычислительной математике и математическом программировании.
Частным случаем двоичного поиска является метод бисекции, который применяется для поиска корней заданной непрерывной функции на заданном отрезке.
Поиск элемента в отсортированном массиве
- Определение значения элемента в середине структуры данных. Полученное значение сравнивается с ключом.
- Если ключ меньше значения середины, то поиск осуществляется в первой половине элементов, иначе — во второй.
- Поиск сводится к тому, что вновь определяется значение серединного элемента в выбранной половине и сравнивается с ключом.
- Процесс продолжается до тех пор, пока не будет найден элемент со значением ключа или не станет пустым интервал для поиска.
Несмотря на то, что код достаточно прост, в нём есть несколько ловушек.
- Код
(first + last) / 2
ошибочен, еслиfirst
иlast
по отдельности умещаются в свой тип, аfirst+last
— нет<ref name="joshua">Extra, Extra — Read All About It: Nearly All Binary Searches and Mergesorts are Broken Шаблон:Wayback // Joshua Bloch, Google Research; перевод — Почти во всех реализациях двоичного поиска и сортировки слиянием есть ошибка Шаблон:Wayback</ref>. Если теоретически возможны массивы столь большого размера, приходится идти на ухищрения:- Использовать код
first + (last - first) / 2
, который точно не приведёт к переполнениям, если имеем дело с неотрицательными целыми числами и first<last.- Если
first
иlast
— указатели или итераторы, такой код единственно правильный, поскольку не нарушает абстракцию (уже операция «указатель + указатель» некорректна). Разумеется, чтобы сохранялась сложность алгоритма, нужны быстрые операции «указатель+число → указатель», «указатель−указатель → число».
- Если
- Если
first
иlast
— типы со знаком, провести расчёт в беззнаковом типе:((unsigned)first + (unsigned)last) / 2
. В Java сработает такой код:(first + last) >>> 1
(знаковое двоичное сложение совпадает с беззнаковым, Java гарантирует такое поведение даже при переполнении, и вся эта формула оперирует знаковыми числами как беззнаковыми). - Написать расчёт на ассемблере, с использованием флага переноса. Что-то наподобие
add eax, b; rcr eax, 1
. А вот длинные типы использовать нецелесообразно,first + (last - first) / 2
быстрее.
- Использовать код
- В двоичном поиске часты ошибки на единицу, и каждая такая ошибка превращается в зацикливание, пропуск или выход за пределы массива. Поэтому важно протестировать такие случаи: пустой массив (
n=0
), один элемент (n=1
), ищем отсутствующее значение (слишком большое, слишком маленькое и где-то в середине), ищем первый и последний элемент. - Иногда требуется, чтобы, если
x
в цепочке существует в нескольких экземплярах, находило не любой, а обязательно первый (как вариант: последний; либо вообще неx
, а следующий за ним элемент).<ref>В C++std::lower_bound
находит первое вхождениеx
, аstd::upper_bound
— элемент, следующий заx
.</ref> Например, функция Шаблон:Cpp из C++ находит первый из равных, а Шаблон:Cpp — элемент, следующий за x. Если не найдено — оба возвращают место, куда вставить.
Учёный Йон Бентли утверждает, что 90 % студентов, разрабатывая двоичный поиск, забывают учесть какое-либо из этих требований. И даже в код, написанный самим Йоном и ходивший из книги в книгу, вкралась ошибка: код не стоек к переполнениям<ref name="joshua"/>.
Пример реализации на Java
int binarySearch(int[] arr, int key) {
int low = 0;
int high = arr.length - 1;
while (low <= high) {
int mid = (low + high) >>> 1;
int midVal = arr[mid];
if (midVal < key)
low = mid + 1;
else if (midVal > key)
high = mid - 1;
else
return mid; // key found
}
return -(low + 1); // key not found.
}
Приложения
Практические приложения метода двоичного поиска разнообразны:
- Широкое распространение в информатике применительно к поиску в структурах данных. Например, поиск в массивах данных осуществляется по ключу, присвоенному каждому из элементов массива (в простейшем случае сам элемент является ключом).
- Также его применяют в качестве численного метода для нахождения приближённого решения уравнений (см. Метод бисекции).
- Метод используется для нахождения экстремума целевой функции и в этом случае является методом условной одномерной оптимизации. Когда функция имеет вещественный аргумент, найти решение с точностью до [math]\displaystyle{ \varepsilon }[/math] можно за время [math]\displaystyle{ \log_2 1 / \varepsilon }[/math]. Когда аргумент дискретен, и изначально лежит на отрезке длины N, поиск решения займёт [math]\displaystyle{ 1 + \log_2N }[/math] времени. Наконец, для поиска экстремума, скажем, для определённости минимума, на очередном шаге отбрасывается тот из концов рассматриваемого отрезка, значение в котором максимально.
См. также
Примечания
Литература
- Шаблон:Source
- Шаблон:Книга
- Шаблон:Книга
- Шаблон:Книга
- Шаблон:Книга
- Шаблон:Книга
- Шаблон:Книга:CLRS
- Шаблон:Книга
- Шаблон:Книга
- Шаблон:Книга
- Шаблон:Книга