Разделяй и властвуй
В этом параграфе вы узнаете об алгоритмах «разделяй и властвуй», которые помогают выполнять поиск по огромным базам данных в миллион раз быстрее, чем алгоритмы исчерпывающего поиска. Вооружившись этой техникой, вы узнаете, что стандартный способ умножать числа (которому вас учили в начальной школе) далеко не самый быстрый. Затем мы применим подход «разделяй и властвуй», чтобы спроектировать быстрые алгоритмы для сортировки. Вы узнаете, что эти алгоритмы оптимальны — то есть даже легендарный ученый Алан Тьюринг не смог бы спроектировать алгоритм сортировки быстрее!
Основная идея
Если вы хотите решить задачу с помощью стратегии «разделяй и властвуй», вам нужно подумать о следующих трёх шагах:
- Разделение задачи на подзадачи поменьше.
- Рекурсивное решение каждой подзадачи.
- Объединение выполненных подзадач в решение изначальной задачи.
Первые два шага — это и есть «разделяй», а последний — «властвуй». Мы продемонстрируем такой подход в нескольких примерах, сложность которых будет возрастать.
Угадать число
Игра «Угадать число» состоит в том, что оппонент загадывает целое число $1 \le x \le n$. Вы задаёте вопрос: «$x=y$?». Оппонент отвечает либо «да», либо «$x<y$» (то есть «мое число меньше»), либо «$x>y$» (то есть «мое число больше»). Ваша задача — получить ответ «да», задав минимальное количество вопросов.
Пусть $n=3$: ваша задача — угадать $1 \le x \le 3$, задав не больше двух вопросов.
Вы можете спросить: «$x=1$?». Если ответ положительный, то вы победили. Но оппонент может ответить: «$x>1$». Вы решаете, что $x$ равен $2$ или $3$, но у вас остаётся только один вопрос. Точно так же вы можете спросить: «$x=3$?». Тогда ваш оппонент может ответить: «$x<3$». В этом случае вы не сможете получить желаемый положительный ответ, задав лишь один вопрос.
Посмотрим, что будет, если вы сначала спросите: «$x=2$?». Если оппонент отвечает, что $x=2$, тогда игра окончена. Если ответ — $x<2$, то вы уже знаете, что $x=1$. Следовательно, второй раз вы просто спрашиваете: «$x=1$?». И теперь вы получаете положительный ответ. Если оппонент ответит, что $x>2$, то вы спрашиваете: «$x=3$?». Ответ на него: «Да».
✒️ Упражнение:
Угадать целое число $1 \le x \le 7$, задав не больше трёх вопросов.
Вы уже могли догадаться, что мы начнём с вопроса: «$x=4$?». Дело в том, что в обоих случаях — $x<4$ и $x>4$ — мы сокращаем пространство поиска с 7 до 3 вариантов (нам уже известно, как решить задачу с $3$ возможными вариантами):
- если $x<4$, то $x$ будет 1, 2 или 3;
- если $x>4$, то $x$ будет 5, 6 или 7.
Это означает, что в обоих случаях вы можете воспользоваться решением разобранного ранее случая $n=3$. Получившийся протокол вопросов показан на рисунке.
Следующий код имитирует процесс угадывания. Функция query
«знает» целое число $x$. Вызов query(y)
сообщает нам: $x=y$, или $x<y$, или $x>y$. Функция guess()
находит число $x$ с помощью вызова query()
. Она вызывается с двумя параметрами: lower
и upper
— так, чтобы $$
\texttt{lower} \le x \le \texttt{upper},
$$ то есть $x$ находится в сегменте $[\texttt{lower},, \texttt{upper}]$. Сначала она рассчитывает середину (middle
) сегмента $[\texttt{lower},, \texttt{upper}]$, затем вызывает $\texttt{query(middle)}$. Если $x<\texttt{middle}$, тогда она продолжает работать с интервалом $[\texttt{lower},, \texttt{middle - 1}]$. Если $x>\texttt{middle}$, тогда она переходит к интервалу $[\texttt{middle}+1,, \texttt{upper}]$.
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) // начальный возможный диапазон значений
Реализуйте этот алгоритм, измените значение $x$ и запустите код, чтобы увидеть последовательность вопросов (удостоверьтесь, что $x$ находится в сегменте, который используется при вызове guess
).
В целом стратегия, угадывающая целое число $1 \le x \le n$, потребует около $\log_2 n$ вопросов. Напомним, что $\log_2 n$ равняется $b$, если $2^b=n$. Это значит, что если мы продолжим делить $n$ на 2, пока не получим 1, будет около $\log_2 n$ операций деления. Важно здесь то, что $\log_2 n$ — медленно растущая функция. К примеру, если $n \le 10^9$, то $\log_2 n < 30$.
Поиск по отсортированным данным
Метод, который мы использовали для угадывания числа, известен как двоичный поиск. Пожалуй, самый важный случай применения двоичного поиска — это поиск по отсортированным данным. Поиск — фундаментальная задача: имея последовательность и элемент $x$, мы хотим проверить, входит ли $x$ в последовательность. Например, 3 входит в последовательность $(7, 2, 5, 6, 11, 3, 2, 9)$, а 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 выполняет линейное сканирование. На это требуется $n$ сравнений при последовательности длиной $n$. Если в последовательность не входит $x$, нам необходимо просканировать все элементы: если мы будем пропускать, то мы не можем точно знать, отсутствует ли $x$.
Ситуация кардинально меняется, если полученные данные отсортированы, то есть составляют собой отсортированную последовательность $a_0, \dotsc, a_{n-1}$ в порядке возрастания.
Оказывается, что в этом случае достаточно около $\log_2 n$ сравнений! Это значительное ускорение: линейный поиск по отсортированному массиву с миллиардом элементов потребует миллиарда сравнений, двоичному же поиску будет достаточно не больше $\log_210^9<30$!
Двоичный поиск
Ваша задача — найти индекс элемента в сортированной последовательности равного $q$.
- Формат ввода: Отсортированный массив $K$ неповторяющихся целых чисел и целое число $q$. Первые две строки ввода содержат целое число $n$ и последовательность $k_0 < k_1 < \dotsc < k_{n-1}$ из $n$ неповторяющихся положительных целых чисел в возрастающем порядке. Следующая строка содержит целое число $q$.
- Формат вывода: Позиция элемента в $K$ равного $q$ или $-1$ при отсутствии такого элемента.
- Ограничения: $1 \le n \le 3 \cdot 10^4$; $1 \le k_i \le 10^9$ для всех $0 \le i < n$; $1 \le q \le 10^9$.
- Примеры
Пример 1
Ввод | Вывод |
---|---|
7 1 3 7 8 9 12 15 8 | 3 |
Пример 2
Ввод | Вывод |
---|---|
7 1 3 7 8 9 12 15 12 | 5 |
Можно решить эту задачу примитивным способом — просканировать массив $K$ (время выполнения составит $O(n)$). Время решения этой задачи для алгоритма BinarySearch
— $O(\log n)$. Он инициализируется при присвоении $minIndex$ значения 0 и $maxIndex$ значения $n-1$. Сначала алгоритм присваивает $midIndex$ значение $(minIndex + maxIndex)/2$, а затем проверяет, больше $q$, чем $K[midIndex]$, или нет. Если $q$ больше, чем это значение, то BinarySearch
проводит итерацию на подмассиве $K$ от minIndex до $midIndex-1$. В ином случае он проводит итерацию на подмассиве $K$ от $midIndex + 1$ до $maxIndex$. В конечном счёте алгоримт определит, находится $q$ в $K$ или нет.
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
Например, если $q = 9$ и $K = [1, 3, 7, 8, 9, 12, 15]$, BinarySearch
сначала задаст следующее: $minIndex=0$, $maxIndex=6$ и $midIndex=3$. Так как $q$ больше, чем $K[midIndex] = 8$, мы рассматриваем подмассив, элементы которого больше $K[midIndex]$, установив $minIndex=4$, и таким образом $midIndex$ перевычисляется как $(4+6)/2 = 5$. В этот раз $q$ меньше, чем $K[midIndex] = 12$, поэтому мы рассматриваем подмассив, элементы которого ниже этого значения. Этот подмассив состоит из одного элемента — $q$.
Время выполнения BinarySearch
составляет $O(\log n)$, так как алгоритм снижает длину подмассива минимум в два раза при каждой итерации цикла while
. Обратите внимание: наша система оценки не может знать, использовали вы быстрый алгоритм с трудоёмкостью $O(\log n)$ для поиска в отсортированном массиве или примитивный алгоритм с трудоёмкостью $O(n)$. Дело в том, что любой программе требуется линейное время для чтения данных ввода. По этой причине мы предлагаем вам решить следующую более общую задачу.
Множественный поиск ключей в отсортированной последовательности
- Вывод: При каждом $q_i$ необходимо проверить, входит ли $q_i$ в $K$.
- Формат ввода: Отсортированный массив $K$ неповторяющихся целых чисел и массив целых чисел $Q=[q_0,\dotsc,q_{m-1}]$. Первые две строки ввода содержат целое число $n$ и последовательность $k_0<k_1< \dotsc < k_{n-1}$ из $n$ неповторяющихся положительных целых чисел в возрастающем порядке. Следующие две строки содержат целое число $m$ и $m$ положительных целых чисел $q_0, q_1, \dotsc, q_{m-1}$.
- Формат вывода: Для всех $i$ от $0$ до $m-1$ выведите индекс $0 \le j \le n-1$, чтобы $k_j=q_i$ или $-1$ при отсутствии такого индекса.
- Ограничения: $1 \le n \le 3 \cdot 10^4$; $1 \le m \le 10^5$; $1 \le k_i \le 10^9$ для всех $0 \le i < n$; $1 \le q_j \le 10^9$ для всех $0 \le j < m$.
- Примеры
Пример 1
Ввод | Вывод |
---|---|
7 1 3 7 8 9 12 15 1 8 | 3 |
Пример 2
Ввод | Вывод |
---|---|
7 1 3 7 8 9 12 15 3 1 12 3 | 0 5 1 |
- Совет: не используйте встроенный двоичный поиск
Двоичный поиск с дублированием
Как пишет автор книги «Искусство программирования» Дональд Кнут: «Хотя основная идея двоичного поиска относительно проста, детали могут быть на удивление сложными». Он подразумевает изменённую версию классической задачи двоичного поиска:
Когда Кнут попросил профессиональных программистов из таких ведущих компаний, как IBM, реализовать эффективный алгоритм двоичного поиска с дублированием, в 90% из них были баги — год за годом. И правда, хотя первый алгоритм двоичного поиска был опубликован в 1946 году, первый алгоритм для поиска с дублированием, в котором не было багов, впервые опубликовали только в 1962 году.
По аналогии с предыдущей задачей здесь мы предлагаем найти $m$ целых чисел, а не одно.
- Формат ввода: Первые две строки ввода содержат целое число $n$ и последовательность $k_0 \le k_1 \le \dotsb \le k_{n-1}$ из $n$ положительных целых чисел в неубывающем порядке. Следующие две строки содержат целое число $m$ и $m$ положительных целых чисел $q_0, q_1, \dotsc, q_{m-1}$.
- Формат вывода: Для всех $i$ от $0$ до $m-1$ вывод индекса $0 \le j \le n-1$ первого встречающегося $q_i$ (то есть $k_j=q_i$) или $-1$ — если такого индекса нет.
- Ограничения: $1 \le n \le 3 \cdot 10^4$; $1 \le m \le 10^5$; $1 \le k_i \le 10^9$ для всех $0 \le i < n$; $1 \le q_j \le 10^9$ для всех $0 \le j < m$.
- Примеры
Пример 1
Ввод | Вывод |
---|---|
7 2 4 4 4 7 7 9 4 9 4 5 2 | 6 1 -1 0 |
Пример 2
Ввод | Вывод |
---|---|
3 1 1 1 3 1 2 3 | 0 -1 -1 |
- Совет: не используйте встроенный двоичный поиск
Решение
У вас есть ключ $q$ и вам необходимо найти первое, самое раннее место, где этот ключ встречается в массиве $K$. Например, если $K={3, 6, 6, 7, 7, 7, 7, 9}$ и ключ $q$ — это $7$, тогда первое место, где он встречается, — это индекс $3$. Разумеется, вы можете найти одно из мест, просто начав двоичный поиск. Чтобы найти первое место, где ключ встречается, вы можете последовательно проверять элемент перед позицией того, который был найден, — что и демонстрируется в выделенных голубым строках приведенного ниже псевдокода.
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
потребует линейное время $O(n)$ вместо логарифмического времени $O(\log n)$. Эта проблема устранена в псевдокоде ниже.
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