3. Модификация двоичного поиска
Теперь модифицируем алгоритм двоичного поиска так, чтобы элементы, в точности равные key, оказывались в правой части списка,
а не в левой, как раньше.
Это потребует изменения неравенства в условии внутри цикла:
def LowerBound(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
На каких значениях left и right закончится данный цикл? A[left] < key, A[right] >= key.
То есть элемент, равный key, можно вставить на место A[right], сохраняя упорядоченность списка, и это минимальная позиция,
куда его можно вставить.
Иными словами, данная функция возвращает «нижнюю границу» для элемента key.
Следует отметить, что поскольку UpperBound возвращает индекс первого элемента, который больше чем key, а LowerBound возвращает
индекс первого элемента, который равен key (а если такого нет — то того, который больше, чем key), то значение разности
UpperBound(A, key) – LowerBound(A, key) равно числу вхождений элемента key в список A.
При помощи LowerBound также можно проверить вхождение элемента key в список A при помощи условия
right < len(A) and A[right] == key