2. Бинарный поиск
Но если исходный массив уже отсортирован, то элемент в нем можно найти гораздо быстрее, если воспользоваться идеей двоичного (бинарного)
поиска. Идея заключается в делении списка пополам, после чего в зависимости от значения медианного элемента в списке мы переходим либо к
левой, либо к правой половине списка. Тем самым, длина части, в которой мы ищем элемент, сокращается в два раза на каждом шаге цикла, а,
значит, общая сложность алгоритма двоичного поиска будет O(log2n).
Итак, перед нами стоит задача — выяснить, содержится ли элемент key в некотором списке, или в его части.
Мы будем сокращать часть списка, в которой мы ищем элемент key. А именно, введем две границы — left и right.
При этом мы будем знать, что элемент A[right] строго больше, чем key, то же самое можно сказать и про элементы, которые правее right.
Про элемент A[left] и те, которые находятся левее него мы будем знать, что все они меньше или равны key.
А вот про элементы, которые лежат строго между A[left] и A[right] (то есть про элементы, чьи индексы больше left, но меньше right), мы ничего
не знаем.
В самом начале мы ничего не знаем про все элементы массива, поэтому присвоим left = -1 и right = len(A).
Можно представить это так — к концам массива добавляются два фиктивных элемента, в левый конец добавляется элемент, в который записывается
минус бесконечность (т. е. значение, заведомо меньшее, чем key), и этот элемент имеет индекс -1, а в правый элемент дописывается элемент,
равный плюс бесконечности, и его индекс равен len(A).
Соответственно, переменные left и right первоначально указывают на эти фиктивные элементы (то есть на самом деле никаких элементов к
массиву добавлять не требуется, мы это делаем лишь мысленно).
Затем разделим отрезок от left до right на две части и возьмем средний элемент между ними. Его индекс равен middle = (left + right) // 2.
Сравним значение этого элемента со значением key.
Если A[middle] строго больше чем key это означает, что сам элемент A[middle] и все, что правее него, должно попасть в правую часть.
Это означает, что нужно сделать присваивание right = middle.
Иначе (если A[middle] <= key), то элемент A[middle] и все, что левее него, должно попасть в левую часть, то есть необходимо присвоить
left = middle.
Будем повторять этот процесс, пока между двумя границами left и right еще есть элементы, то есть пока right > left + 1.
Получаем следующий алгоритм:
left = -1
right = len(A)
while right > left + 1:
middle = (left + right) // 2
if A[middle] > key:
right = middle
else:
left = middle
Что будет после завершения этого алгоритма?
left и right указывают на два соседних элемента, при этом A[right] > key, A[left] <= key.
Таким образом, если элемент key содержится в списке, то A[left] == key.
Правда, возможна ситуация, когда left == -1 (если в списке A все элементы строго больше key), поэтому для ответа на вопрос «содержится ли
в списке A элемент key» необходимо проверить условие:
left >= 0 and A[left] == key
Что же можно сказать про значение right?
Это минимальный элемент списка, который строго больше, чем key.
Иными словами, на место элемента A[right] можно вставить элемент со значением key (сдвинув при этом всю правую часть списка на один элемент), сохраняя упорядоченность списка, при этом right есть самая правая позиция, куда можно вставить в список элемент key, сохраняя упорядоченность.
В этом случае говорят, что значение right является «верхней границей» для элемента key:
правее этой позиции нельзя вставить элемент key, сохраняя список упорядоченным.
Вот функция, которая в заданном списке A находит «верхнюю границу» для заданного элемента key:
def UpperBound(A, key):
left = -1
right = len(A)
while right > left + 1:
middle = (left + right) // 2
if A[middle] > key:
right = middle
else:
left = middle
return right