7.1. Двоичный поиск

Разделяй и властвуйРазделяй и властвуй

В этом параграфе вы узнаете об алгоритмах «разделяй и властвуй», которые помогают выполнять поиск по огромным базам данных в миллион раз быстрее, чем алгоритмы исчерпывающего поиска. Вооружившись этой техникой, вы узнаете, что стандартный способ умножать числа (которому вас учили в начальной школе) далеко не самый быстрый. Затем мы применим подход «разделяй и властвуй», чтобы спроектировать быстрые алгоритмы для сортировки. Вы узнаете, что эти алгоритмы оптимальны — то есть даже легендарный ученый Алан Тьюринг не смог бы спроектировать алгоритм сортировки быстрее!

Основная идеяОсновная идея

Если вы хотите решить задачу с помощью стратегии «разделяй и властвуй», вам нужно подумать о следующих трёх шагах:

• Разделение задачи на подзадачи поменьше.
• Рекурсивное решение каждой подзадачи.
• Объединение выполненных подзадач в решение изначальной задачи.

Первые два шага — это и есть «разделяй», а последний — «властвуй». Мы продемонстрируем такой подход в нескольких примерах, сложность которых будет возрастать.

Угадать числоУгадать число

Игра «Угадать число» состоит в том, что оппонент загадывает целое число . Вы задаёте вопрос: «?». Оппонент отвечает либо «да», либо «» (то есть «мое число меньше»), либо «» (то есть «мое число больше»). Ваша задача — получить ответ «да», задав минимальное количество вопросов.

Пусть : ваша задача — угадать , задав не больше двух вопросов.

Вы можете спросить: «?». Если ответ положительный, то вы победили.Но оппонент может ответить: «». Вы решаете, что равен или , но у вас остаётся только один вопрос. Точно так же вы можете спросить: «?». Тогда ваш оппонент может ответить: «». В этом случае вы не сможете получить желаемый положительный ответ, задав лишь один вопрос.

Посмотрим, что будет, если вы сначала спросите: «?». Если оппонент отвечает, что , тогда игра окончена. Если ответ — , то вы уже знаете, что . Следовательно, второй раз вы просто спрашиваете: «?». И теперь вы получаете положительный ответ.Если оппонент ответит, что , то вы спрашиваете: «?». Ответ на него: «Да».

✒️ Упражнение:
Угадать целое число , задав не больше трёх вопросов.

Вы уже могли догадаться, что мы начнём с вопроса: «?». Дело в том, что в обоих случаях — и — мы сокращаем пространство поиска с 7 до 3 вариантов (нам уже известно, как решить задачу с возможными вариантами):

• если , то будет 1, 2 или 3;
• если , то будет 5, 6 или 7.

Это означает, что в обоих случаях вы можете воспользоваться решением разобранного ранее случая . Получившийся протокол вопросов показан на рисунке.

Следующий код имитирует процесс угадывания. Функция query «знает» целое число . Вызов query(y) сообщает нам: , или , или . Функция guess() находит число с помощью вызова query(). Она вызывается с двумя параметрами: lower и upper— так, чтобы

то есть находится в сегменте . Сначала она рассчитывает середину (middle) сегмента , затем вызывает . Если , тогда она продолжает работать с интервалом . Если , тогда она переходит к интервалу .

query(y):
    x = 1618235
    if x == y:
        return 'equal'
    if x < y:
        return 'smaller'
    else:
        return 'greater'


guess(lower, upper):
    middle = (lower + upper) / 2 // целочисленное деление
    answer = query(middle)
    // можно напечатать запрос и соответствующий результат
    if answer == 'equal':
        return
    if answer == 'smaller':
        guess(lower, middle - 1)
    else:
        guess(middle + 1, upper)


guess(1, 2097151) // начальный возможный диапазон значений

Реализуйте этот алгоритм, измените значение и запустите код, чтобы увидеть последовательность вопросов (удостоверьтесь, что находится в сегменте, который используется при вызове guess).

В целом стратегия, угадывающая целое число , потребует около вопросов. Напомним, что равняется , если . Это значит, что если мы продолжим делить на 2, пока не получим 1, будет около операций деления. Важно здесь то, что — медленно растущая функция. К примеру, если , то .

Поиск по отсортированным даннымПоиск по отсортированным данным

Метод, который мы использовали для угадывания числа, известен как двоичный поиск. Пожалуй, самый важный случай применения двоичного поиска — это поиск по отсортированным данным. Поиск — фундаментальная задача: имея последовательность и элемент , мы хотим проверить, входит ли в последовательность. Например, 3 входит в последовательность , а 4 — не входит. Зная о важности задачи по поиску, неудивительно, что методы для её решения есть почти во всех языках программирования.

print(3 in [7, 2, 5, 6, 11, 3, 2, 9])
print(4 in [7, 2, 5, 6, 11, 3, 2, 9])

Что происходит внутри, когда мы вызываем метод in? Ожидаемо, Python выполняет линейное сканирование. На это требуется сравнений при последовательности длиной . Если в последовательность не входит , нам необходимо просканировать все элементы: если мы будем пропускать, то мы не можем точно знать, отсутствует ли .

Ситуация кардинально меняется, если полученные данные отсортированы, то есть составляют собой отсортированную последовательность в порядке возрастания.

Оказывается, что в этом случае достаточно около сравнений! Это значительное ускорение: линейный поиск по отсортированному массиву с миллиардом элементов потребует миллиарда сравнений, двоичному же поиску будет достаточно не больше !

Двоичный поискДвоичный поиск

Ваша задача — найти индекс элемента в сортированной последовательности равного .

• Формат ввода: Отсортированный массив неповторяющихся целых чисел и целое число . Первые две строки ввода содержат целое число и последовательность из неповторяющихся положительных целых чисел в возрастающем порядке. Следующая строка содержит целое число .
• Формат вывода: Позиция элемента в равного или при отсутствии такого элемента.
• Ограничения: ; для всех ; .
• Примеры

Пример 1Пример 1

Ввод	Вывод
7 1 3 7 8 9 12 15 8	3

Пример 2Пример 2

Ввод	Вывод
7 1 3 7 8 9 12 15 12	5

Можно решить эту задачу примитивным способом — просканировать массив (время выполнения составит ). Время решения этой задачи для алгоритма BinarySearch — . Он инициализируется при присвоении значения 0 и значения . Сначала алгоритм присваивает значение , а затем проверяет, больше , чем , или нет. Если больше, чем это значение, то BinarySearch проводит итерацию на подмассиве от minIndex до . В ином случае он проводит итерацию на подмассиве от до . В конечном счёте алгоримт определит, находится в или нет.

BinarySearch(K[0..n−1], q)
    minIndex = 0
    maxIndex = n−1
    while maxIndex >= minIndex:
        midIndex = (minIndex+maxIndex) / 2 // целочисленное деление
        if K[midIndex] = q:
            return midIndex
        else K[midIndex] < q:
            minIndex = midIndex + 1
        else:
            maxIndex = midIndex - 1
    return -1

Например, если и , BinarySearch сначала задаст следующее: , и . Так как больше, чем , мы рассматриваем подмассив, элементы которого больше , установив , и таким образом перевычисляется как . В этот раз меньше, чем , поэтому мы рассматриваем подмассив, элементы которого ниже этого значения. Этот подмассив состоит из одного элемента — .

Время выполнения BinarySearch составляет , так как алгоритм снижает длину подмассива минимум в два раза при каждой итерации цикла while. Обратите внимание: наша система оценки не может знать, использовали вы быстрый алгоритм с трудоёмкостью для поиска в отсортированном массиве или примитивный алгоритм с трудоёмкостью . Дело в том, что любой программе требуется линейное время для чтения данных ввода. По этой причине мы предлагаем вам решить следующую более общую задачу.

Множественный поиск ключей в отсортированной последовательностиМножественный поиск ключей в отсортированной последовательности

• Вывод: При каждом необходимо проверить, входит ли в .

• Формат ввода: Отсортированный массив неповторяющихся целых чисел и массив целых чисел
  . Первые две строки ввода содержат целое число и последовательность из неповторяющихся положительных целых чисел в возрастающем порядке. Следующие две строки содержат целое число и положительных целых чисел .
• Формат вывода: Для всех от до выведите индекс , чтобы или при отсутствии такого индекса.
• Ограничения: ; ; для всех ; для всех .
• Примеры

Пример 1Пример 1

Ввод	Вывод
7 1 3 7 8 9 12 15 1 8	3

Пример 2Пример 2

Ввод	Вывод
7 1 3 7 8 9 12 15 3 1 12 3	0 5 1

• Совет: не используйте встроенный двоичный поиск

Двоичный поиск с дублированиемДвоичный поиск с дублированием

Как пишет автор книги «Искусство программирования» Дональд Кнут: «Хотя основная идея двоичного поиска относительно проста, детали могут быть на удивление сложными». Он подразумевает изменённую версию классической задачи двоичного поиска:

Когда Кнут попросил профессиональных программистов из таких ведущих компаний, как IBM, реализовать эффективный алгоритм двоичного поиска с дублированием, в 90% из них были баги — год за годом. И правда, хотя первый алгоритм двоичного поиска был опубликован в 1946 году, первый алгоритм для поиска с дублированием, в котором не было багов, впервые опубликовали только в 1962 году.

По аналогии с предыдущей задачей здесь мы предлагаем найти целых чисел, а не одно.

• Формат ввода: Первые две строки ввода содержат целое число и последовательность из положительных целых чисел в неубывающем порядке. Следующие две строки содержат целое число и положительных целых чисел .
• Формат вывода: Для всех от до вывод индекса первого встречающегося (то есть ) или — если такого индекса нет.
• Ограничения: ; ; для всех ; для всех .
• Примеры

Пример 1Пример 1

Ввод	Вывод
7 2 4 4 4 7 7 9 4 9 4 5 2	6 1 -1 0

Пример 2Пример 2

Ввод	Вывод
3 1 1 1 3 1 2 3	0 -1 -1

• Совет: не используйте встроенный двоичный поиск

РешениеРешение

У вас есть ключ и вам необходимо найти первое, самое раннее место, где этот ключ встречается в массиве . Например, если и ключ — это , тогда первое место, где он встречается, — это индекс . Разумеется, вы можете найти одно из мест, просто начав двоичный поиск. Чтобы найти первое место, где ключ встречается, вы можете последовательно проверять элемент перед позицией того, который был найден, — что и демонстрируется в выделенных голубым строках приведенного ниже псевдокода.

NaiveBinarySearchWithDuplicates(K[0..n−1], q)
    minIndex = 0
    maxIndex = n−1
    while maxIndex >= minIndex:
        midIndex = (minIndex + maxIndex) / 2
        if K[midIndex] = q:
            top = midIndex
            while top > 0 and K[top − 1] = K[top]:
                top = top - 1
            return top
        if K[midIndex] < q:
            minIndex = midIndex + 1
        else:
            maxIndex = midIndex − 1
    return -1

💡 Остановитесь и подумайте:
Каково время выполнения этого алгоритма?

Этот алгоритм может существенно замедлиться при массиве с большим количеством повторов. Например, если повторяющийся элемент занимает половину массива, то NaiveBinarySearchWithDuplicates потребует линейное время вместо логарифмического времени . Эта проблема устранена в псевдокоде ниже.

NaiveBinarySearchWithDuplicates(K[0..n−1], q)
    minIndex = 0
    maxIndex = n−1
    result = -1
    while maxIndex >= minIndex:
        midIndex = (minIndex + maxIndex) / 2
        if K[midIndex] = q:
            maxIndex = midIndex - 1
            result = midIndex
        else if K[midIndex] < q:
            minIndex = midIndex + 1
        else:
            maxIndex = midIndex − 1
    return result