Бинарный поиск (binary search)

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

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

Какую задачу он решает?

Задан отсортированный массив и искомое значение. Необходимо выяснить, содержит ли массив искомое значение и если содержит, то вернуть его индекс.

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

Как он работает?

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

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

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

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

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

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

Реализация на языке 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:

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