[Verse 1]
Got a sorted array and I need to find
A value hidden somewhere inside
Linear search is slow, binary's better
But interpolation makes me a go-getter
Calculate the position, don't just divide by two
Use the value's proportion to guide me through
High minus low times target minus low
Divided by high value minus low value, let's go
[Chorus]
Interpolate, don't just estimate
Jump closer to the target, calculate the rate
Probe position equals low plus the fraction
Better than binary when data's in action
Interpolate, don't just estimate
Uniform distribution, that's the key trait
O of log log n when the spacing is clean
Most efficient search that you've ever seen
[Verse 2]
Start with low index at zero position
High index pointing at the last transmission
Check if target's between the boundary values
If it's outside the range, then the search through
Calculate probe position with the magic formula
Low plus the ratio, that's the criteria
If probe equals target, then we found our prize
If target's smaller, search the left side
[Chorus]
Interpolate, don't just estimate
Jump closer to the target, calculate the rate
Probe position equals low plus the fraction
Better than binary when data's in action
Interpolate, don't just estimate
Uniform distribution, that's the key trait
O of log log n when the spacing is clean
Most efficient search that you've ever seen
[Bridge]
When data's uniform, we shine the brightest
Random distribution makes the worst case tightest
Falls back to linear when the spread is crazy
But with even spacing, performance ain't lazy
Phone book pages, salary ranges
Sequential data where the pattern never changes
[Verse 3]
Update the boundaries after every probe
If target's greater, move low to the node
If target's lesser, move high to the left
Keep interpolating till there's nothing left
Worst case linear, best case logarithmic
Average case performance is quite algorithmic
Remember the assumption that makes this work fine
Data distribution must be in a line
[Chorus]
Interpolate, don't just estimate
Jump closer to the target, calculate the rate
Probe position equals low plus the fraction
Better than binary when data's in action
Interpolate, don't just estimate
Uniform distribution, that's the key trait
O of log log n when the spacing is clean
Most efficient search that you've ever seen
[Outro]
Interpolation search, the smart way to find
When your data's uniform and well-defined
Jump with precision, not just hope and prayer
Mathematical magic gets you right there