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

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

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

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

Решение оформим в виде функции:

def search0(haystack, needle): ...

Мы знаем, что искомый элемент (если он есть) находится на отрезке массива между номерами left (включительно) и right (исключительно), где:

left = 0
right = len(haystack)

Алгоритм бинарного поиска состоит в последовательном сужении диапазона между left и right (на каждом шагу — примерно в два раза) по следующему принципу.

Пусть m = (left+right)//2 (это — примерно середина между left и right). У нас есть три ситуации:

  1. haystack[m] < needle
  2. haystack[m] > needle
  3. haystack[m] == needle

В первой ситуации мы можем сделать вывод о том, что искомый элемент (если он есть) находится на промежутке от m+1 (включительно) до right (исключительно).

Во второй ситуации искомый элемент (опять же, при его наличии) находится между left (включительно) и m (исключительно).

В третьей ситуации мы нашли то, что искали.

Поэтому напрашивается следующий алгоритм:

def search0(haystack, needle):
    left  = 0
    right = len(haystack)
    
    while right - left > 0:
        m = (left + right) // 2
        if   haystack[m] < needle: left  = m+1
        elif haystack[m] > needle: right = m
        else: return m
    
    ## эту строчку можно и не писать (результат функции по-умолчанию равен None)
    return None

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

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

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

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

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

Поиск первого среди равных

Немного усложним задачу (как выяснится чуть позже, решение от этого усложнения только упростится). Потребуем, чтобы в случае наличия нескольких элементов, равных needle, алгоритм выдавал номер самого первого из них. Например, результат вычисления

search1([1,2,2,2,3],2)

должен быть равен 1 (первая двойка находится в массиве именно под номером 1).

Анализ, аналогичный приведённому в предыдущем разделе, говорит о том, что есть две кардинально разные ситуации:

  1. haystack[m] < needle
  2. haystack[m] >= needle

В первом случае искомый элемент, как и прежде, находится между m+1 и right. А вот во втором случае всё несколько хуже: искомый элемент находится между left и m+1. Хуже эта ситуация тем, что разность right-left при заменах вида:

if haystack[m] < needle: left  = m+1
else:                    right = m+1

не изменяется в случае m+1 == right. А такое наблюдается при right-left == 1 или же right-left == 2.

Есть два очевидных выхода из этой ситуации:

  1. Заменить условие цикла right-left>0 на right-left>2. После отдельно обработать ситуации right-left == 1 и right-left == 2.
  2. Заменить m = (left + right) // 2 на m = (left + right - 1) // 2.

Остановимся на втором решении: оно банально проще.

def search1(haystack, needle):
    left  = 0
    right = len(haystack)
    
    while right - left > 1:  ## тут 0 поменялся на 1
        m = (left + right - 1) // 2
        if haystack[m] < needle: left  = m+1
        else:                    right = m+1
    
    ## случай right - left == 1
    if right > left and haystack[left] == needle: return left

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

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

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

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

def search2(haystack, needle, keyfunc):
    left  = 0
    right = len(haystack)
    
    while right - left > 1:
        m = (left + right - 1) // 2
        if keyfunc(haystack[m]) < needle: left  = m+1
        else:                             right = m+1
    
    if right > left and keyfunc(haystack[left]) == needle: 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 = search2(sorted_people, 'Чапаев Василий Иванович', name)

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