Loading AI tools
поиск по линейному массиву Из Википедии, свободной энциклопедии
Двоичный (бинарный) поиск (также известен как метод деления пополам или дихотомия) — классический алгоритм поиска элемента в отсортированном массиве (векторе), использующий дробление массива на половины. Используется в информатике, вычислительной математике и математическом программировании.
Двоичный поиск | |
---|---|
| |
Предназначение | Алгоритм поиска |
Структура данных | Массив |
Худшее время | O(log n) |
Лучшее время | O(1) |
Среднее время | O(log n) |
Затраты памяти | O(1) |
Медиафайлы на Викискладе |
Частным случаем двоичного поиска является метод бисекции, который применяется для поиска корней заданной непрерывной функции на заданном отрезке.
Несмотря на то, что код достаточно прост, в нём есть несколько ловушек.
(first + last) / 2
ошибочен, если first
и last
по отдельности умещаются в свой тип, а first+last
— нет[1]. Если теоретически возможны массивы столь большого размера, приходится идти на ухищрения:
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
, а следующий за ним элемент).[2] Например, функция std::lower_bound
из C++ находит первый из равных, а std::upper_bound
— элемент, следующий за x. Если не найдено — оба возвращают место, куда вставить.Учёный Йон Бентли утверждает, что 90 % студентов, разрабатывая двоичный поиск, забывают учесть какое-либо из этих требований. И даже в код, написанный самим Йоном и ходивший из книги в книгу, вкралась ошибка: код не стоек к переполнениям[1].
Практические приложения метода двоичного поиска разнообразны:
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.