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

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

!!! question

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

![Пример данных для двоичного поиска](../assets/media/image513.jpeg)

Как показано на рисунке ниже, сначала инициализируются указатели $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>"
    ![Процесс двоичного поиска](../assets/media/image515.jpeg)

=== "<2>"
    ![binary_search_step2](../assets/media/image517.jpeg)

=== "<3>"
    ![binary_search_step3](../assets/media/image519.jpeg)

=== "<4>"
    ![binary_search_step4](../assets/media/image521.jpeg)

=== "<5>"
    ![binary_search_step5](../assets/media/image523.jpeg)

=== "<6>"
    ![binary_search_step6](../assets/media/image525.jpeg)

=== "<7>"
    ![binary_search_step7](../assets/media/image527.jpeg)

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

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

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

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

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

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

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

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

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

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

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

![Два определения интервалов](../assets/media/image529.jpeg)

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

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

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

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

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