AlgoThrive
← All searching algorithms

Jump Search

CheckingRuled outFound

array

target = 18
2
4
6
9
12
15
18
20
0
1
2
3
4
5
6
7

pseudocode

jumpSearch(a, target)
  step = floor(sqrt(n)); prev = 0
  while a[min(step, n)-1] < target
    prev = step; step += floor(sqrt(n))
    if prev >= n return -1
  while a[prev] < target
    prev++
    if prev == min(step, n) return -1
  if a[prev] == target return prev
  return -1

Frame 1 / 6

Block size √8 ≈ 2

jumping blocks of size 2

4

Pick a value that is in the array — or one that isn't, to watch the search fail.

3–16 integers between 1 and 20 — the array is sorted for you, because binary search needs ordered data.