Разделяй и властвуй
В этом параграфе вы узнаете об алгоритмах «разделяй и властвуй», которые помогают выполнять поиск по огромным базам данных в миллион раз быстрее, чем алгоритмы исчерпывающего поиска. Вооружившись этой техникой, вы узнаете, что стандартный способ умножать числа (которому вас учили в начальной школе) далеко не самый быстрый. Затем мы применим подход «разделяй и властвуй», чтобы спроектировать быстрые алгоритмы для сортировки. Вы узнаете, что эти алгоритмы оптимальны — то есть даже легендарный ученый Алан Тьюринг не смог бы спроектировать алгоритм сортировки быстрее!
Основная идея
Если вы хотите решить задачу с помощью стратегии «разделяй и властвуй», вам нужно подумать о следующих трёх шагах:
- Разделение задачи на подзадачи поменьше.
- Рекурсивное решение каждой подзадачи.
- Объединение выполненных подзадач в решение изначальной задачи.
Первые два шага — это и есть «разделяй», а последний — «властвуй». Мы продемонстрируем такой подход в нескольких примерах, сложность которых будет возрастать.
Угадать число
Игра «Угадать число» состоит в том, что оппонент загадывает целое число . Вы задаёте вопрос: «?». Оппонент отвечает либо «да», либо «» (то есть «мое число меньше»), либо «» (то есть «мое число больше»). Ваша задача — получить ответ «да», задав минимальное количество вопросов.
Пусть : ваша задача — угадать , задав не больше двух вопросов.
Вы можете спросить: «?». Если ответ положительный, то вы победили.Но оппонент может ответить: «». Вы решаете, что равен или , но у вас остаётся только один вопрос. Точно так же вы можете спросить: «?». Тогда ваш оппонент может ответить: «». В этом случае вы не сможете получить желаемый положительный ответ, задав лишь один вопрос.
Посмотрим, что будет, если вы сначала спросите: «?». Если оппонент отвечает, что , тогда игра окончена. Если ответ — , то вы уже знаете, что . Следовательно, второй раз вы просто спрашиваете: «?». И теперь вы получаете положительный ответ.Если оппонент ответит, что , то вы спрашиваете: «?». Ответ на него: «Да».
✒️ Упражнение:
Угадать целое число , задав не больше трёх вопросов.
Вы уже могли догадаться, что мы начнём с вопроса: «?». Дело в том, что в обоих случаях — и — мы сокращаем пространство поиска с 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
|
Ввод |
Вывод |
|
7 |
3 |
Пример 2
|
Ввод |
Вывод |
|
7 |
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
|
Ввод |
Вывод |
|
7 |
3 |
Пример 2
|
Ввод |
Вывод |
|
7 |
0 |
- Совет: не используйте встроенный двоичный поиск
Двоичный поиск с дублированием
Как пишет автор книги «Искусство программирования» Дональд Кнут: «Хотя основная идея двоичного поиска относительно проста, детали могут быть на удивление сложными». Он подразумевает изменённую версию классической задачи двоичного поиска:
Когда Кнут попросил профессиональных программистов из таких ведущих компаний, как IBM, реализовать эффективный алгоритм двоичного поиска с дублированием, в 90% из них были баги — год за годом. И правда, хотя первый алгоритм двоичного поиска был опубликован в 1946 году, первый алгоритм для поиска с дублированием, в котором не было багов, впервые опубликовали только в 1962 году.
По аналогии с предыдущей задачей здесь мы предлагаем найти целых чисел, а не одно.
- Формат ввода: Первые две строки ввода содержат целое число и последовательность из положительных целых чисел в неубывающем порядке. Следующие две строки содержат целое число и положительных целых чисел .
- Формат вывода: Для всех от до вывод индекса первого встречающегося (то есть ) или — если такого индекса нет.
- Ограничения: ; ; для всех ; для всех .
- Примеры
Пример 1
|
Ввод |
Вывод |
|
7 |
6 |
Пример 2
|
Ввод |
Вывод |
|
3 |
0 |
- Совет: не используйте встроенный двоичный поиск
Решение
У вас есть ключ и вам необходимо найти первое, самое раннее место, где этот ключ встречается в массиве . Например, если и ключ — это , тогда первое место, где он встречается, — это индекс . Разумеется, вы можете найти одно из мест, просто начав двоичный поиск. Чтобы найти первое место, где ключ встречается, вы можете последовательно проверять элемент перед позицией того, который был найден, — что и демонстрируется в выделенных голубым строках приведенного ниже псевдокода.
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