Published by Dimitris Kougioumtzis · Updated
Estimate a position from the value range. Best suited to uniformly distributed sorted values. Input is sorted before searching.
Estimate a probe from the target's numeric position between endpoint values, then narrow the interval.
When to use Interpolation search
Exploring distribution-sensitive search.
Choosing an alternative
Binary search keeps a logarithmic bound without assuming evenly spaced values.
Worked example: input and state changes
Example input
38, 12, 65, 8, 43, 27, 91, 19 | 43
These checkpoints follow the actual example timeline. State details show the stored values and decisions; use the visualization to inspect every intervening step.
Step 0: Initial state.
State at this checkpoint
{ "values": [ 8, 12, 19, 27, 38, 43, 65, 91 ], "active": [] }Step 1: Estimate index 2 from the value range.
State at this checkpoint
{ "values": [ 8, 12, 19, 27, 38, 43, 65, 91 ], "active": [ 2 ] }Step 2: Estimate index 4 from the value range.
State at this checkpoint
{ "values": [ 8, 12, 19, 27, 38, 43, 65, 91 ], "active": [ 4 ] }Step 3: Estimate index 5 from the value range.
State at this checkpoint
{ "values": [ 8, 12, 19, 27, 38, 43, 65, 91 ], "active": [ 5 ] }Step 4: Found 43 at index 5.
State at this checkpoint
{ "values": [ 8, 12, 19, 27, 38, 43, 65, 91 ], "active": [ 5 ] }
Expected final state
Found 43 at index 5.
Complexity and input bounds
Family: Searching. Time complexity: O(n) worst.
Space complexity: O(1) auxiliary space.
Working-space bounds describe algorithm state and any explicitly noted output, excluding the visualization's saved timeline. Recording frames can use more memory than running the function alone. Here n is sequence length, V and E are vertex and edge counts, and other parameters refer to the named input dimensions.
2–24 comma-separated integers between 0 and 99. Follow with | target.
The playground validates these limits before starting. Downloaded functions are callable implementations, with parameter and output-buffer contracts in their comments; they do not all repeat the playground's input validation.
Common mistakes and limitations
Equal endpoints need a division guard; clustered values can cause linear work.
Further reading
For background on algorithm analysis and the JavaScript function interface:
- MIT OpenCourseWare: algorithm design and analysis foundations
- MDN: JavaScript function parameters and return values
Editorial and testing approach · Browse all algorithm guides
Complete JavaScript implementation
1 2 3 4 5 6 7 8 9 10 11 12 | // Requires ascending values from 0 to 99, with at most 24 entries. Returns a found index or -1. Reference snippets assume validated playground inputs. Fixed scratch buffers have 256 slots. Sorting variants may use a different traversal strategy than the animation. function algorithm(a, n, target) { let l = 0; let r = n - 1; while (l <= r && target >= a[l] && target <= a[r]) { if (a[l] == a[r]) { if (a[l] == target) { return l; } return -1; } let offset = (target - a[l]) * (r - l); let range = a[r] - a[l]; let pos = l + Math.floor(offset / range); if (a[pos] == target) { return pos; } if (a[pos] < target) { l = pos + 1; } else { r = pos - 1; } } return -1; } |
Source
Primary research source for the algorithm or its underlying method. The playground is a bounded teaching implementation, not the publication's original program.
- Addressing for Random-Access Storage
W. W. Peterson (1957). Research paper.