Итак, вопрос в том, чтобы найти диапазон числа в отсортированном массиве.

Например: в списке [1,2,3,4,4,4,4,4,4,5] диапазон 4 составляет от 3 до 9.

Чтобы получить O (log n), воспользуемся двоичным поиском. На самом деле мы будем использовать его дважды, чтобы найти верхний и нижний диапазон.

Чтобы получить более низкий диапазон, нам нужно переместиться в «Влево» массива сверхурочно (так как он отсортирован). Небольшая модификация двоичного поиска даст нам самое левое значение:

while lower_bound < upper_bound:
        mid = (upper_bound+lower_bound)/2
        if B <= A[mid]:
            upper_bound = mid
        else:
            lower_bound= mid+1

(upper_bound + lower_bound) / 2 даст нам нижнее значение целого числа.

Таким образом, для каждой итерации, если A [mid] равно ‹= целевому числу, начальный диапазон числа находится либо в A [mid], либо слева от него. Итак, мы устанавливаем верхнюю границу на mid (а не на mid-1, так как текущий элемент сам может быть верхней границей).

Если число больше среднего, нижняя граница должна быть mid + 1, это не должно быть проблемой.

Затем нам нужно найти верхнюю границу, поэтому нам нужно сдвинуть вправо от массива.

середина = (верхняя_ граница + нижняя_ граница) / 2 + 1

Кроме того, мы не будем изменять значение, хранящееся в lower_bound. Поскольку upper_bound будет в индексе lower_bound или справа от него.

    while  lower_bound < upper_bound:
        mid = (lower_bound+upper_bound)/2+1
        if B < A[mid]:
            upper_bound = mid-1
        else:
            lower_bound = mid

Итак, если цель ниже, upper_bound = mid-1 (это нижняя часть массива).

Если элемент (B) равен или больше, чем A [mid], мы должны установить lower_bound как mid (не mid + 1, поскольку этот индекс сам может содержать верхний диапазон числа).

Вот и все, ребята!