hello-algo/ru/docs/chapter_searching/binary_search.md

Двоичный поиск

Двоичный (бинарный) поиск -- это эффективный алгоритм поиска, основанный на стратегии «разделяй и властвуй». Он использует упорядоченность данных, сокращая на каждом шаге область поиска вдвое, пока не будет найден целевой элемент или область поиска не станет пустой.

!!! question

Дан массив `nums` длиной $n$, элементы которого расположены в порядке возрастания и не повторяются. Необходимо найти и вернуть индекс элемента `target` в этом массиве. Если массив не содержит этот элемент, вернуть $-1$. Пример показан на рисунке ниже.

Как показано на рисунке ниже, сначала инициализируются указатели i = 0 и j = n - 1, которые указывают на первый и последний элементы массива и представляют область поиска [0, n - 1]. Обратите внимание, что квадратные скобки обозначают замкнутый интервал, включающий граничные значения.

Затем в цикле выполняются следующие два шага:

1. Вычисляется индекс средней точки m = \lfloor (i + j)/2 \rfloor, где \lfloor \: \rfloor обозначает операцию округления вниз.
2. Определяется соотношение между nums[m] и target, выделяются три случая:
   1. Если nums[m] < target, то target находится в интервале [m + 1, j], поэтому выполняется i = m + 1.
   2. Если nums[m] > target, то target находится в интервале [i, m - 1], поэтому выполняется j = m - 1.
   3. Если nums[m] = target, то target найден, и возвращается индекс m.

Если массив не содержит целевой элемент, область поиска в конечном итоге сократится до пустой. В этом случае возвращается -1.

=== "<1>"

=== "<2>"

=== "<3>"

=== "<4>"

=== "<5>"

=== "<6>"

=== "<7>"

Следует отметить, что, поскольку i и j имеют тип int, сумма i + j может превысить допустимый диапазон значений типа int. Чтобы избежать переполнения, обычно для вычисления средней точки используется формула m = \lfloor i + (j - i)/2 \rfloor.

Ниже приведен пример кода.

[file]{binary_search}-[class]{}-[func]{binary_search}

Временная сложность составляет $O(\log n)$: в цикле двоичного поиска область поиска сокращается вдвое на каждом шаге, поэтому количество итераций равно \log_2 n.

Пространственная сложность составляет $O(1)$: указатели i и j занимают постоянное количество памяти.

Методы представления интервалов

Кроме указанного выше двойного замкнутого интервала, существует также левозамкнутый правооткрытый интервал [0, n), т. е. левая граница включается, а правая -- нет. В этом представлении интервал [i, j) пуст, когда i = j.

На основе этого представления можно реализовать двоичный поиск с аналогичной функциональностью.

[file]{binary_search}-[class]{}-[func]{binary_search_lcro}

В двух представлениях интервалов инициализация, условия цикла и операции сокращения интервала в алгоритме двоичного поиска различаются, как показано на рисунке ниже.

Поскольку в представлении «двойной замкнутый интервал» обе границы определены как замкнутые, операции сокращения интервала с помощью указателей i и j также симметричны. Это снижает вероятность ошибок, поэтому обычно рекомендуется использовать запись «двойной замкнутый интервал».

Преимущества и ограничения

Двоичный поиск обладает хорошей производительностью как по времени, так и по пространству.

• Двоичный поиск отличается высокой эффективностью по времени. При большом объеме данных логарифмическая временная сложность имеет значительное преимущество. Например, при размере данных n = 2^{20} линейный поиск требует 2^{20} = 1048576 итераций, тогда как двоичный поиск -- всего \log_2 2^{20} = 20 итераций.
• Двоичный поиск, в отличие от некоторых других алгоритмов поиска (например, хеш-поиска), не требует дополнительного пространства и поэтому более экономичен в плане использования памяти.

Тем не менее двоичный поиск не подходит для всех случаев по следующим основным причинам.

• Двоичный поиск применим только к упорядоченным данным. Если входные данные неупорядоченные, то их сортировка специально для использования двоичного поиска не оправдана. Это связано с тем, что временная сложность алгоритмов сортировки обычно составляет O(n \log n), что выше, чем у линейного и двоичного поиска. В сценариях с частыми добавлениями элементов для поддержания упорядоченности массива необходимо вставлять элементы в определенные позиции, что имеет временную сложность O(n) и также является весьма затратным.
• Двоичный поиск применим только к массивам, поскольку требует скачкообразного (непрерывного) доступа к элементам. В связных списках выполнение скачкообразного доступа менее эффективно, поэтому такой поиск не подходит для применения в связных списках и структурах данных, основанных на них.
• При небольших объемах данных линейный поиск более эффективен. В линейном поиске на каждом этапе требуется только одна операция сравнения; в двоичном поиске требуется одна операция сложения, одна операция деления, от одной до трех операций сравнения и одна операция сложения (вычитания), всего от четырех до шести элементарных операций. Поэтому, когда объем данных n невелик, линейный поиск оказывается быстрее двоичного.