Бинарный поиск (binary search)
Published: 2023-11-25 21:49:51


От также известен под названиями: двоичный поиск, метод деления пополам, метод дихотомии.

На собеседовании вас скорее всего не будут спрашивать напрямую: “Напишите бинарный поиск”. Но могут спросить задачу, решение которой практически полностью повторяет этот алгоритм, с некоторыми изменениями. Поэтому его нужно знать наизусть и уметь его написать за пару минут без подсказок и гугления.
>  Какую задачу он решает?
>  Задан **отсортированный** массив и искомое значение. Необходимо выяснить, содержит ли массив искомое значение и если содержит, то вернуть его **индекс**.

Тут ключевой момент это то, что массив **отсортирован**. Это может служить также подсказкой на собеседовании. Если в условии дан именно **отсортированный** массив, подумайте, может можно применить метод бинарного поиска. Или же массив можно сначала отсортировать, а потом применить метод бинарного поиска.
>  Как он работает?

 1. Инициализируем левый и правый индексы — началом и концом массива соответственно.

 2. Находим середину между левым и правым индексами.

 3. Если значение в середине совпадает с искомым, то мы возращаем его индекс. Поиск завершен.

 4. Если значение в **середине меньше искомого**, то из-за того, что массив отсортирован — **искомого значения точно нет слева**. Т.к. слева все элементы еще меньше. Поэтому искомое значение если и содержиться в массиве — то справа. Поэтому мы может **сократить в два раза область поиска** и искать только справа. Для этого мы передвигаем левый индекс в середину и переходим к пункту 2.

 5. Если значение в середине больше искомого. То искать нужно слева (справа все значения еще больше). Поэтому передвигаем правый индекс в середину и переходим к пункту 2.

Алгоритм работает за **O(log(n))** из-за того, что мы каждый раз **в два раза сокращаем область поиска**. Тогда как линейный поиск в массиве работает за O(n) (когда мы последовательно сравниваем все элементы массива, пока не найдем заданный).

На данном примере я показал, как искомое значение мы нашли всего за 2 итерации.

Дан отсортированный массив:

[3, 7, 18, 26, 29, 43]. Требуется проверить, содержится ли в нем значение 29 и если да, то какой индекс у элемента со значением 29?

Ответ: индекс 4.

![](https://cdn-images-1.medium.com/max/2000/1*tSx9dkR1qL3UvQSRUj3cUQ.png)

Реализация на языке Java:

```java
      public static int binarySearch(int[] array, int target) {
        int left = 0;
        int right = array.length - 1;
        while (left <= right) {
    
            //Находим середину
            //Для большиго размера массивов лучше использовать
            //int mid = left + (right - left) / 2; Для предотвращения переполнения
            int mid = (left + right) / 2;
    
            //Значение в середине равно искомому значению
            if (array[mid] == target) {
              return mid;
            }
    
            //Искомое значение меньше, чем элемент в середине.
            //Следовательно искомое значение слева.
            //Поэтому двигаем правый индекс. 
            //Иначе, искомое значение справа и двигаем левый индекс.
            if (array[mid] > target) {
              right = mid - 1;
            } else {
              left = mid + 1;
            }
        }
        return -1;
      }
```

Реализация на языке Python:

```python
    def binarySearch(array, target):
      left = 0
      right = len(array) - 1
      while left <= right:
        mid = (left + right) // 2
        if target == array[mid]:
          return mid
        if target < array[mid]:
          right = mid - 1
        else:
          left = mid + 1
      return -1
```