Loading…
Loading…
Like binary search, but estimates the probe position from the target's value — near O(log log n) on uniformly distributed data.
Estimate position of 53 by interpolation.
Tip: click any bar to make it the target.
1int interpolationSearch(int[] arr, int target) {2 int left = 0, right = arr.length - 1; // Full search range3 while (left <= right && target >= arr[left] && target <= arr[right]) { // Target within range4 int pos = left + (target-arr[left])*(right-left)/(arr[right]-arr[left]); // Estimate probe position5 if (arr[pos] == target) return pos; // Match found6 else if (arr[pos] < target) left = pos + 1; // Search upper part7 else right = pos - 1; // Search lower part8 }9 return -1; // Not in array10}