Кратко — ошибка в обновлении границ: при использовании полуоткрытого интервала $[lo,hi)$ нельзя писать $lo=mid$ или $hi=mid$, потому что при $hi-lo=1$ будет $\text{mid}=lo$ и присваивание $lo=mid$ не сдвинет границу (зациклит). Временная сложность алгоритма при корректной реализации — $O(\log n)$.
Подробно и исправления:
1) Причина ошибки
- В цикле вычисляется $\text{mid}=(lo+hi)//2$. Если $hi-lo=1$, то $\text{mid}=lo$. При ветке $a[\text{mid}]<x$ код делает $lo=\text{mid}$, границы не меняются и цикл бесконечен. Пример: $hi-lo=1$ (разрыв один элемент) — нет прогресса.
2) Правильный простой фикс (вернёт любой индекс с совпадением)
- Для полуоткрытого интервала $[lo,hi)$ обновления должны быть:
- если $a[\text{mid}]<x$: $lo=\text{mid}+1$ - если $a[\text{mid}]>x$: $hi=\text{mid}$ - если равно — можно вернуть $\text{mid}$ - Тогда гарантированно происходит сужение интервала и сложность $O(\log n)$.
Пример исправленного кода (любая найденная позиция):
def binsearch(a, x):
lo, hi = 0, len(a)
while lo < hi:
mid = (lo + hi) // 2
if a[mid] == x:
return mid
if a[mid] < x:
lo = mid + 1
else:
hi = mid
return -1
3) Если нужен левый (первый) индекс при повторяющихся элементах
- Использовать поиск границы: сужаем так, чтобы в конце $lo$ был индекс первой позиции $\ge x$. После цикла проверяем равенство.
Код для левого вхождения:
def bisect_left(a, x):
lo, hi = 0, len(a)
while lo < hi:
mid = (lo + hi) // 2
if a[mid] < x:
lo = mid + 1
else:
hi = mid
return lo if lo < len(a) and a[lo] == x else -1
Аналогично для правого вхождения можно настраивать условия.