Двоичный поиск в отсортированном массиве — это стандартный алгоритм поиска компонентов в отсортированном массиве, который применяет деление массива пополам.
Алгоритм двоичного поиска имеет следующие синонимы: бинарный поиск, способ половинного деления, дихотомия.
Общая структура алгоритма
Способ двоичного поиска применяется как быстрая версия поискового алгоритма в предварительно прошедшем сортировку массиве. Он приобрёл широкую популярность, поскольку обладает самой маленькой высотой алгоритма из всех допустимых и некоторыми достоинствами его вычислительных параметров. И кроме того, если брать не числовые алгоритмы, он обладает свойством рекурсивности, то есть его легко записать. Базовой чертой алгоритма является дробление массива на равные половинки и затем, выполнении рекурсивного поиска в одной из половин. Ниже приведён пример поиска элемента «четыре» в массиве:
Рисунок 1. Поиск элемента «четыре» в массиве. Автор24 — интернет-биржа студенческих работ
Впервые этот способ был упомянут на занятиях в школе Мура Джона Мокли в середине пятидесятых годов прошлого века. Сначала алгоритм предназначался лишь для массивов длины:
2k−12k−1,
но в конце пятидесятых годов прошлого века Д.Г.Лемер разработал методику, которая позволяла работать с массивами любых размеров. Позднее Герман Боттенбрух реализовал этот алгоритм на языке Алгол, где сравнение выполнялось в конце и увеличивало число итераций алгоритма на единицу, но при этом уменьшало количество операций сравнения до одного на каждую итерацию. Конкурентом данного способа считается метод линейного поиска, что означает полный перебор вариантов. Он обладает следующей сложностью вычислений:
O(n)O(n),
но способен работать на массивах, которые были упорядочены в произвольном порядке. Сравнение особенностей использования этих методик показывает, что метод линейного поиска имеет преимущества при:
- Поиске в небольших по размерам массивах.
- При выполнении достаточно малого количества поисковых операций.
- При выполнении поиска в случае потока.
Двоичный поиск предполагает предварительную сортировку со сложностью, определяемую выражением:
O(nlog2n)O(nlog2fOn)
Бинарный поиск удобен при больших размерах массивов и многократном его повторении. История формирования и развития методики двоичного поиска, следующая. В 1971-ом году А.К. Чандра представил методику однородного двоичного поиска Дональду Кнуту, опубликовавшему этот метод в своей научной работе.
Затем появился метод троичного поиска, при котором выполнялось деление отрезка на три участка. Он используется для определения местоположения функционального экстремума.
Метод интерполирующего поиска, при котором участок поиска не делился на два, а выполнялось предсказание позиции компонента поиска на базе разницы значений. Данный метод обладает большим быстродействием, при достаточно равномерном распределении элементов. Средняя сложность задаётся выражением:
O(loglogn)O(logfOlogfOn).
Но при самом плохом раскладе, сложность будет равна:
O(n)O(n).
В 1986-ом году Бернар Шазеллем и Леонидас Дж. Губайс предложили вариант, который назвали дробный спуск, и который ускорил двоичный поиск в многомерных массивах.
Близким вариантом к двоичному поиску в массиве является способ бисекции или способ половинного деления. Его основным отличием считается вычисление величины функции вместо определения компонента массива согласно его индексации, и, кроме того, применение действительных чисел как аргументов, являющихся индексами компонентов массива. По своим свойствам, алгоритм может определяться как в рекурсивной, так и в итеративной форме. Ядро для вычислений в обеих формах одно и тоже, но при рекурсии имеется добавочная нагрузка, которая состоит в вызове функций и сохранении их стека.
Математическое представление алгоритма
В качестве исходных данных возьмём одномерный массив nn чисел
xì, ì=0…n−1xì, ì=0…n−1,
в котором выполнено упорядочивание по не убыванию или же по не возрастанию. Кроме того, имеем число АА, которое требуется отыскать в данном массиве. Данные, подлежащие вычислению, это индексный номер компонента, который равняется требуемому. Или же отрицательный ответ при отсутствии такого компонента. Формулировка методики следующая. Компоненты на всех этапах алгоритма представляются как непрерывный отрезок массива. Каждая пара содержит сумму компонентов, которые её составляют. На очередном шаге на пары делятся уже данные суммы, а также компоненты, не вошедшие в уже известные суммы, и так далее. На каждом шаге итерации выполняется одно действие, а именно вычисляется среднее арифметическое левого и правого индексов:
mk = lk + rk2mk = lk + rk2
Где символами lk, rk, mklk, rk, mk обозначена индексация левого и правого окончания, а также середины данного отрезка массива при кк-ом шаге итерации.
Первоначально выполняется поиск по всем элементам массива, поэтому
l0 = 0, r0 = n−1l0=0, r0=n−1
Ядром вычислений способа двоичного поиска являются операции сравнения и определения середины отрезка, выполняемые рекуррентно для постоянно уменьшающегося в размерах массива. Общее число операций сложения, умножения и сравнения прямо пропорционально числу шагов итерации, а оно не может быть более, чем:
[log2n][log2fOn].
Само определение алгоритма подразумевает наличие в нём рекурсивных вызовов одного и того же действия для постоянно уменьшающихся массивов. При это не применяются никакие стандартные макрооперации.
Выполнение последовательного алгоритма можно разбить на следующие этапы:
Этап 1. Выполнение инициализации концов отрезка с помощью концов массива:
l0 = 0, r0 = n−1l0 = 0, r0 = n−1
Этап 2. В случае, когда lk\gtrklk\gtrk, то это означает завершение поиска как неуспешного. В противном случае ищется позиция середины отрезка массива как целая часть от половины суммы позиций его окончаний:
mk = [lk + rk2]mk = [lk + rk2].
Этап 3. В случае, когда xmk\ltAxmk\ltA, тогда определяем:
lk:=mk+1lk:=mk+1 и возвращаемся ко второму этапу.
Этап 4. В случае, когда xmk = Axmk = A, поиск завершается ввиду отсутствия искомого значения и возвращается номер позиции mkmk.
