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

Задача эффективного поиска данных, хранящихся в массиве, существенно упрощается, если данные в массиве расположены не произвольно, а упорядочены (для определённости — по неубыванию).

Простейшая разновидность бинарного поиска

Для начала поставим простую задачу: есть упорядоченный массив haystack и некий объект needle (на который единственное ограничение — должна быть возможность сравнивать его с элементами массива при помощи операций больше/меньше). Нужно найти границу между элементами, строго меньшими needle, и элементами, большими или равными ему.

Для удобства будем считать len(haystack) == N и мысленно пронумеруем все границы между элементами массива (а также — слева и справа от них) числами от 0 до N. Заметим, что для любого x (в пределах от 0 до N-1) граница с номером x находится непосредственно левее элемента с номером x.

Рассмотрим следующий алгоритм:

def binsearch(haystack, needle):
    left  = 0
    right = len(haystack)
  
    while right > left:
        mid = (left + right) // 2
        if haystack[mid] < needle:  left = mid + 1
        else:                      right = mid

    return left

Очевидно, что если этот алгоритм завершил работу, то его результатом как раз является искомая граница. Поэтому единственный важный вопрос, связанный ним: «а всегда ли заканчивается цикл?» Ответ на этот вопрос утвердительный по следующим соображениям:

  1. Если right>left, то mid<right.
  2. При этом m+1>left.
  3. Отсюда следует, что на каждом шаге разность right-left уменьшается хотя бы на 1. Поэтому всегда оставаться положительной она не может.

Теперь поймём, насколько бинарный поиск эффективнее полного перебора. Для этого нужно заметить, что разность right-left на каждом шагу уменьшается не меньше, чем в два раза. Поэтому количество шагов, требующееся для завершения работы алгоритма на массиве размера n не превосходит ни одно целое k, для которого 2**k > n.

В частности, увеличение количества данных в два раза влечёт увеличение времени работы не больше чем на время выполнения одного шага алгоритма (если оставить за рамками модели наблюдающееся на практике увеличение времени доступа к элементу массива с увеличением размера массива, то время выполнения одного шага не зависит от размера массива).

Например, массив размера миллиард элементов будет обработан бинарным поиском не дольше чем за 30 шагов. Нетрудно заметить, что 30 шагов, в каждом из которых не более двух сравнений и ещё чуть-чуть арифметики, существенно приятнее, чем миллиард сравнений при поиске полным перебором.

Наконец, отметим, что результат работы этого алгоритма совпадает с рангом элемента needle — количеством элементов массива haystack, меньших needle.

Поиск по ключу

На практике вышеизложенные задачи поиска почти не встречаются: обычно мы ищем не положение «Василия Ивановича Чапаева номер паспорта 1234 567890» в массиве людей, упорядоченном по ФИО и номеру паспорта, а номер паспорта человека по имени «Василий Иванович Чапаев».

Те данные, которые мы подаём на вход процедуре поиска, традиционно называются ключом поиска (вспомните терминологию, связанную с типом данных «словарь»). В примере с Василием Ивановичем ключом поиска является ФИО. Отображение, сопоставляющее единице данных соответствющий ей ключ, называется ключевой функцией.

Ниже приведена версия процедуры бинарного поиска, принимающая на вход ключевую функцию. При этом преполагается, что массив haystack упорядочен по ключу.

def binsearch_key(haystack, needle, key):
    left  = 0
    right = len(haystack)
  
    while right > left:
        mid = (left + right) // 2
        if key(haystack[mid]) < needle:  left = mid + 1
        else:                           right = mid

    return left

И заодно приведём пример использования (с тем самым Василием Ивановичем):

def name(human): return human[0]+' '+human[1]+' '+human[2]

## все совпадения с реальными людьми случайны!
people = [
    ('Чапаев',  'Василий', 'Иванович', 1234, 567890),
    ('Сидоров', 'Иван',    'Петрович', 3210, 456789),
    ('Нектов',  'Некто',   'Нектович', 1111, 111112),
]

sorted_people = sorted(people, key=name)

index = binsearch_key(sorted_people, 'Чапаев Василий Иванович', name)

print('Номер паспорта Василия Ивановича:', *sorted_people[index][3:])

Функция вместо массива

Вообще говоря, в бинарном поиске можно вместо массива использовать любую монотонную функцию. Как, например, в следующем примере:

def binsearch_fn(haystack, needle):
    fn, left, right  = haystack
  
    while right > left:
        mid = (left + right) // 2
        if fn(mid) < needle:  left = mid + 1
        else:                right = mid

    return left

## эта функция вычисляет верхний целочисленный корень числа бинарным поиском
def root(n):
    return binsearch_fn( (lambda x: x*x, 0, n), n )

Что интересно, обе ранее рассмотренные разновидности бинарного поиска тривиально выражаются при помощи этой:

def binsearch(haystack, needle):
    def get(x): return haystack[x]
    return binsearch_fn( (get, 0, len(haystack)), needle )

def binsearch_key(haystack, needle, key):
    def get(x): return key(haystack[x])
    return binsearch_fn( (get, 0, len(haystack)), needle )