Loading…
Loading…
On a sorted array, jumps ahead by fixed blocks of √n until it passes the target, then scans the last block linearly.
Jump in blocks of √n = 3 for 53.
Tip: click any bar to make it the target.
1int jumpSearch(int[] a, int target) {2 int n = a.length, step = (int)Math.sqrt(n), prev = 0;3 while (prev < n && a[Math.min(step, n)-1] < target) {4 prev = step; step += (int)Math.sqrt(n);5 if (prev >= n) return -1;6 }7 for (int i = prev; i < Math.min(step, n); i++)8 if (a[i] == target) return i;9 return -1;10}