Бинарный поиск

ОПИСАНИЕ ГРУППЫ ЗАДАЧ
Тип поискового алгоритма, который последовательно делит пополам заранее отсортированный массив данных, чтобы обнаружить нужный элемент.

Бинарный поиск подходит для нахождения позиций элемента в упорядоченном массиве: в этом случае он эффективнее линейного, поскольку массив данных на каждом шаге разделяется надвое и одна половина сразу отбрасывается.
Задача
Есть упорядоченный массив целых чисел , нужно определить, есть ли в нём число X.

def binary_search(array, x):
    left: int = 0
    right: int = len(array)
    while left < right:
        midian = (left + right) // 2
        if array[midian] == x:
            return True
        elif array[midian] < x:
            left = midian + 1
        else:
            right = midian
    return False


if __name__ == "__main__":
    array: int = [5, 7, 9, 12, 15, 18, 19, 20, 22]
    x: int = 20
    print(binary_search(array, x))
Задача
Дан упорядоченный массив и число X, нужно найти максимальный элемент массива, не превосходящего X.
Если такого элемента не существует, вернуть -1.

def max_to_border(array, x):
    if not array or array[0] > x:
        return -1

    left: int = 0
    right: int = len(array)
    while left + 1 < right:
        midian = (left + right) // 2
        if array[midian] <= x:
            left = midian
        else:
            right = midian
    return array[left]


if __name__ == "__main__":
    array: int = [5, 7, 9, 12, 15, 18, 19, 20, 22]
    x: int = 14
    print(max_to_border(array, x))
Разновидности алгоритма
На основе бинарного поиска разработано несколько дополнительных разновидностей поисковых алгоритмов:

  • однородный бинарный поиск,
  • троичный поиск,
  • интерполирующий поиск,
  • дробный спуск
однородный бинарный поиск
Поиск, при котором аргумент поиска А сравнивается с ключом Ki, где i — золотое сечение интервала (оно выбирается так, чтобы отношение длины большего отрезка к длине всего интервала равнялось отношению длины меньшего отрезка к длине большего отрезка);
троичный поиск
Поиск, когда интервал делится на три части вместо двух. Обычно применяется для поиска положения экстремума функции;
интерполирующий поиск
Поиск, который предсказывает позицию нужного элемента на основе разницы значений. Эффективен, если элементы распределены достаточно равномерно;
дробный спуск
Применяется для ускорения двоичного поиска в многомерных массивах данных, и другие.