DEV Community

faangmaster
faangmaster

Posted on

Бинарный поиск (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;
      }
Enter fullscreen mode Exit fullscreen mode

Реализация на языке 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
Enter fullscreen mode Exit fullscreen mode

Image of Timescale

🚀 pgai Vectorizer: SQLAlchemy and LiteLLM Make Vector Search Simple

We built pgai Vectorizer to simplify embedding management for AI applications—without needing a separate database or complex infrastructure. Since launch, developers have created over 3,000 vectorizers on Timescale Cloud, with many more self-hosted.

Read full post →

Top comments (0)

Postmark Image

Speedy emails, satisfied customers

Are delayed transactional emails costing you user satisfaction? Postmark delivers your emails almost instantly, keeping your customers happy and connected.

Sign up

Retry later