Besides binary search there are other ways to search sorted data. Each wins under certain conditions: jump search (O(sqrt n)) when access is forward-only, interpolation on uniformly distributed values (average O(log log n)), exponential search for sequences of unknown length. The basics are in the topic on binary search.
Jump search
We split the array into blocks of size step. While the last element of a block is below x, we jump to the next one; when a[cur - 1] >= x, the target is in the current block and we scan it linearly. Probes are n / step + step, minimal at step = sqrt n: O(sqrt n). Memory O(1). It is slower than binary search but only moves forward: useful where going back is expensive (tape, some iterator types).
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