Бинарный поиск (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