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[] arr, int target) {2 if (arr[0] == target) return 0; // Check first element3 int n = arr.length, bound = 1; // Start bound at 14 while (bound < n && arr[bound] < target) bound *= 2; // Double bound past target5 int left = bound/2, right = Math.min(bound, n-1); // Binary search range6 while (left <= right) {7 int mid = (left + right) / 2; // Middle index8 if (arr[mid] == target) return mid; // Match found9 else if (arr[mid] < target) left = mid + 1; // Discard left half10 else right = mid - 1; // Discard right half11 }12 return -1; // Not in array13}