Кроме бинарного поиска, у отсортированных данных есть и другие способы поиска. Каждый выигрывает при определённых условиях: прыжковый поиск (O(sqrt n)) — когда доступ только вперёд, интерполяционный — на равномерно распределённых значениях (в среднем O(log log n)), экспоненциальный — для последовательностей неизвестной длины. Основа в теме бинарный поиск.
Прыжковый поиск (jump search)
Делим массив на блоки по step. Пока последний элемент блока меньше x, прыгаем к следующему; когда a[cur - 1] >= x, цель в текущем блоке, и мы ищем в нём линейно. Число проверок n / step + step, минимум при step = sqrt n: O(sqrt n). Память O(1). Медленнее бинарного, но двигается только вперёд: полезно там, где возврат дорог (лента, некоторые типы итераторов).
import math
def linear(a, x):
probes = 0
for i, v in enumerate(a):
probes += 1
if v == x:
return i, probes
return -1, probes
def jump(a, x):
n = len(a)
step = math.isqrt(n)
probes, prev, cur = 0, 0, step
while prev < n: # jump over whole blocks
probes += 1
if a[min(cur, n) - 1] >= x:
break
prev, cur = cur, cur + step
for i in range(prev, min(cur, n)): # scan inside the block
probes += 1
if a[i] == x:
return i, probes
if a[i] > x:
break
return -1, probes