Jump Search
A compromise between linear and binary: hop in √n blocks to find the right neighbourhood, then scan linearly inside it. Useful when jumping backwards is expensive.
- Category
- Searching
- Time complexity
- O(√n)
- Space complexity
- O(1)
Pseudocode
block ← √n jump while block end < target linear scan within block return index or not found
Reference implementation
def jump_search(a, t):
step = int(len(a) ** 0.5)
i = 0
while a[min(i+step, n)-1] < t:
i += step
for k in range(i, min(i+step, n)):
if a[k] == t: return k