Написать эту заметку меня побудили три обстоятельства.
Давайте же решим эту жуткую задачу.
Любопытно, что когда задачу бисекции задают на собеседованиях, её редко формулируют исчерпывающе: что именно мы ищем, если искомых элементов нет? если их, наоборот, много? если искомый ключ выпадает за пределы массива?.. Давайте чётко оговорим, что мы ищем.
Дан сортированный массив a и ключ k. Следует найти такой индекс i,
чтобы при вставке ключа k в a на позицию i, отсортированность
массива a сохранялась. Если значения k в массиве уже имеются, то
вставлять надо справа от них.
Из этого условия сразу понятно, что делать если k меньше всех
элементов. Ответом должен быть 0. И что делать, если k больше
всех элементов. Тут ответ должен быть len(a).
Естественно, все приведённые ниже выкладки можно проделать и для других условий (скажем, для вставки слева). Это не столь принципиально.
При написании таких алгоритмов, очень помогает понятие инварианта. Кстати, оно поможет вам убедить в своей правоте недалёкого оппонента.
Введём индексы l и r. Договоримся, что они всегда будут отвечать
следующим условиям:
Для всех i < l: a[i] <= k
Для всех i > r: a[i] > k
Это и есть инвариант. (Обратите внимание на строгость/нестрогость неравенств. Здесь и далее это очень существенно.)
Начальные условия будут гарантировать выполнение инварианта:
l = 0 # индекс первого элемента
r = len(a) - 1 # индекс последнего элемента
То есть нет ни одного элемента с i < l или i > r. Это
гарантирует, что инвариант не нарушается.
Условие завершения поиска:
r < l
То есть, все элементы рассмотрены. Любой индекс удовлетворяет
одному из условий: i < l, i > r.
Ответом будет индекс l.
Это становится очевидным, если посмотреть на наш инвариант и условие выхода. Ясно, что после всех итераций у нас будет выполняться условие:
Для всех i < l: a[i] <= k
Для всех i >= l: a[i] > k
То есть l — это индекс первого элемента, который строго больше k.
Именно в это место надо вставить k по условию задачи.
Реализация проста:
def bis(a, k):
l = 0
r = len(a) - 1
while r >= l:
m = (r + l) // 2
if a[m] <= k:
l = m + 1
else:
r = m - 1
return l
Строго говоря, «m=(r+l)//2» лучше писть как «m=r-(r-l)//2»;
чтобы не было риска выйти за пределы int. Но для Python это не актуально.
И, заметьте, она корректно решает поставленную задачу и на пустом массиве и в других пограничных случаях. Это следует из того, что алгоритм никогда не нарушает инвариант и завершается в правильный момент.
Несмотря на то, что тут есть операций с индексами, которые могут
показаться опасными, алгоритм работает правильно. Без каких-либо
дополнительных проверок. Он не зацикливается, не выходит за пределы
массива (за исключением случая, когда k больше всех элементов a,
но это оговорено в условии).
Не верите? Посмотрите на него внимательно. А если есть сомнения, давайте его погоняем.
Вот код, с помощью которого я гонял алгоритм:
#!/usr/bin/python2
# coding: utf8
'''
Метод деленеия пополам
Будем искать правую границу
лемма:
a[i] <= k для всех i < L
a[i] > k для всех i > R
в начале
L = 0
R = len(a) - 1 # индекс последнего элемента
в конце
R < L # т.е. рассмотрены все элементы
ответ в L
'''
from collections import defaultdict
def pr(a, l, r, m=None):
markers = defaultdict(list)
for k in 'lrm':
if locals()[k] is not None:
markers[locals()[k]].append(k.upper())
print ''.join(
map(lambda x: '\033[1;32m%3s\033[0m' % ''.join(markers.get(x, [])),
range(-1, len(a) + 1))
)
print ' _ ' + ' '.join(map(lambda x: '%2d' % x, a)) + ' _'
def bis(a, k):
l = 0
r = len(a) - 1
pr(a, l, r)
while r >= l:
m = (r + l) // 2
pr(a, l, r, m)
if a[m] <= k:
l = m + 1
else:
r = m - 1
pr(a, l, r)
return l
for a, k in (
((1, 2, 3, 3, 4, 5, 6, 8, 9), 3),
((1, 2, 3, 3, 4, 5, 6, 8, 9), 7),
((1, 2, 3, 3, 4, 5, 6, 8, 9), 1),
((1, 2, 3, 3, 4, 5, 6, 8, 9), 0),
((1, 2, 3, 3, 4, 5, 6, 8, 9), 10),
((1,), 3),
((1,), 0),
):
print "==========="
print "k = %d" % k
i = bis(a, k)
print "result = %d" % i
# вы можете также убедиться, что вставка
# даёт абсолютно правильный результат
#a = list(a)
#a.insert(i, k)
#print repr(a)
А вот результат:
===========
k = 3
L R
_ 1 2 3 3 4 5 6 8 9 _
L M R
_ 1 2 3 3 4 5 6 8 9 _
L R
_ 1 2 3 3 4 5 6 8 9 _
L M R
_ 1 2 3 3 4 5 6 8 9 _
L R
_ 1 2 3 3 4 5 6 8 9 _
LM R
_ 1 2 3 3 4 5 6 8 9 _
LR
_ 1 2 3 3 4 5 6 8 9 _
LRM
_ 1 2 3 3 4 5 6 8 9 _
R L
_ 1 2 3 3 4 5 6 8 9 _
result = 4
===========
k = 7
L R
_ 1 2 3 3 4 5 6 8 9 _
L M R
_ 1 2 3 3 4 5 6 8 9 _
L R
_ 1 2 3 3 4 5 6 8 9 _
L M R
_ 1 2 3 3 4 5 6 8 9 _
L R
_ 1 2 3 3 4 5 6 8 9 _
LM R
_ 1 2 3 3 4 5 6 8 9 _
R L
_ 1 2 3 3 4 5 6 8 9 _
result = 7
===========
k = 1
L R
_ 1 2 3 3 4 5 6 8 9 _
L M R
_ 1 2 3 3 4 5 6 8 9 _
L R
_ 1 2 3 3 4 5 6 8 9 _
L M R
_ 1 2 3 3 4 5 6 8 9 _
LR
_ 1 2 3 3 4 5 6 8 9 _
LRM
_ 1 2 3 3 4 5 6 8 9 _
R L
_ 1 2 3 3 4 5 6 8 9 _
result = 1
===========
k = 0
L R
_ 1 2 3 3 4 5 6 8 9 _
L M R
_ 1 2 3 3 4 5 6 8 9 _
L R
_ 1 2 3 3 4 5 6 8 9 _
L M R
_ 1 2 3 3 4 5 6 8 9 _
LR
_ 1 2 3 3 4 5 6 8 9 _
LRM
_ 1 2 3 3 4 5 6 8 9 _
R L
_ 1 2 3 3 4 5 6 8 9 _
result = 0
===========
k = 10
L R
_ 1 2 3 3 4 5 6 8 9 _
L M R
_ 1 2 3 3 4 5 6 8 9 _
L R
_ 1 2 3 3 4 5 6 8 9 _
L M R
_ 1 2 3 3 4 5 6 8 9 _
L R
_ 1 2 3 3 4 5 6 8 9 _
LM R
_ 1 2 3 3 4 5 6 8 9 _
LR
_ 1 2 3 3 4 5 6 8 9 _
LRM
_ 1 2 3 3 4 5 6 8 9 _
R L
_ 1 2 3 3 4 5 6 8 9 _
result = 9
===========
k = 3
LR
_ 1 _
LRM
_ 1 _
R L
_ 1 _
result = 1
===========
k = 0
LR
_ 1 _
LRM
_ 1 _
R L
_ 1 _
result = 0
Никогда не пишите бисекцию самостоятельно. Она уже есть
во всех языках в стандартных библиотеках. В Python —
это модуль bisect, в STL — std::binary_search и
вариации.
Бинарный поиск очень часто спрашивают на собеседованиях. Причём, очень часто интервьюеры хотят странного.
Я видел случаи, когда интервьюеры хотят, чтобы в реализации были проверки на выходы за пределы массива.
Тут они, конечно, не правы. Никакие проверки не нужны. У нас есть инвариант, есть начальные установки и есть условие завершения. Наши индексы математически не могут выйти за пределы массива.
Строго говоря, если искомое значение больше либо равно
самому большому элементы массива, то l выйдет
за пределы, но это произойдёт на последней итерации
и рассматривать этот элемент мы не будем.
Если они не верят в математику, то можно показать им любую реализацию.
Тут речь идёт о том, что если искомое значение повторяется много раз, а вы ищите любое совпадение, то завершать поиск надо на первом же равенстве.
Ну что тут сказать. С одной стороны, строго говоря, это не задача бинарного поиска (из-за слова любое в условии). Возможно, интервьюер очень хитрый и подловил вас на невнимательности.
Но с другой стороны, я никогда не видел в реальной жизни алгоритма с равенством. Почему так происходит?
Тут много причин.
Наверно, первая: это "усовершенствование" не меняет асимптотику (если, конечно, у нас не какой-то очень специфический случай, см. ниже)
Следующая причина: потому, что когда речь идёт о сортированном массиве с большим количеством повторяющихся элементов, то все подходы меняются. И это изменение напрямую связано с тем, что за элементы в массиве.
Скажем, если у вас есть список людей, отсортированный по полу в порядке М-Ж, то вам не нужна бисекция, чтобы найти произвольного мужчину: просто возьмите первого человека. А для произвольной женщины: просто возьмите последнего человека. Этот подход можно усложнять, если у вас есть какие-то дополнительные условия, но суть остаётся та же: вы отталкиваетесь от знания природы элементов.
Поэтому, в таких случаях люди не используют бинарный поиск, алгоритмы с равенством не встречаются в природе и человека легко подловить тут на невнимательности.
Хотя, мне частенько кажется, что такие варианты задачек появляются не столько для того, чтобы подловить соискателя, сколько от того, что интервьюер не умеет правильно сформулировать условие или имеет странные представления о данных и алгоритмах.