Jump Search
Optimal for Sorted Arrays. Jumps ahead by fixed steps (√n) then performs linear search.
Enter target and search
1function jumpSearch(arr, x, n):
2 step = sqrt(n)
3 prev = 0
4 while arr[min(step, n)-1] < x:
5 prev = step
6 step += sqrt(n)
7 if prev >= n:
8 return -1
9
10 while arr[prev] < x:
11 prev++
12 if prev == min(step, n):
13 return -1
14
15 if arr[prev] == x:
16 return prev
17 return -1
Complexity
TimeO(√n)
SpaceO(1)