Loading…
Loading…
Doubles an index bound until it overshoots the target, then binary-searches the found range — great for unbounded or very large sorted inputs.
Check a[0] = 6 first.
Tip: click any bar to make it the target.
1int exponentialSearch(int[] a, int target) {2 if (a[0] == target) return 0;3 int n = a.length, bound = 1;4 while (bound < n && a[bound] < target) bound *= 2;5 int lo = bound/2, hi = Math.min(bound, n-1);6 while (lo <= hi) {7 int mid = (lo + hi) / 2;8 if (a[mid] == target) return mid;9 else if (a[mid] < target) lo = mid + 1;10 else hi = mid - 1;11 }12 return -1;13}