Interpolation Search — Searching

🌟(Interpolation Search)

Imagine you have a telephone directory sorted alphabetically — names starting from A at the top and Z at the bottom.
Now, suppose you’re looking for someone whose name begins with “S”.
Would you start searching from A? Of course not!
You’d probably open the book near the end because you estimate where the name might be based on the alphabet order.

That’s exactly what Interpolation Search does — it’s a clever way to search in a sorted list by estimating where your target value might be, rather than blindly jumping to the middle like Binary Search.

🧠 The Core Idea

Interpolation Search is like an upgraded version of Binary Search.
Binary Search always splits the list in half — no matter what the values are.
But Interpolation Search tries to be smarter by guessing where the key could be, based on its value.

It works best when:

The list is sorted, and
The data is uniformly distributed (values are spread out evenly).

📊 How It Works (Step-by-Step)

Let’s say you have a sorted array:

[10, 20, 30, 40, 50, 60, 70, 80, 90, 100]

And you’re searching for the number 70.

Start with two ends:

low = 0 (first index)
high = 9 (last index)

Estimate the position of your key using this formula: [
pos = low + \frac{(key – arr[low]) \times (high – low)}{arr[high] – arr[low]}
] This formula predicts where in the array the key might be, depending on how far it is between the lowest and highest values. Plug in the numbers:
[
pos = 0 + \frac{(70 – 10) \times (9 – 0)}{100 – 10} = \frac{60 \times 9}{90} = 6
]
So, it jumps directly to index 6 — which holds 70! 🎯
Check:

If arr[pos] == key, you’re done!
If arr[pos] < key, search in the right section.
If arr[pos] > key, search in the left section.

This continues until the key is found or the range becomes empty.

🧩 Diagram: Interpolation Search

Here’s a simple visual to help you picture it:

Index:  0   1   2   3   4   5   6   7   8   9
Array: [10, 20, 30, 40, 50, 60, 70, 80, 90, 100]
                   ↑
         Estimated position for key = 70

Instead of jumping to the middle like Binary Search (which would check index 4 or 5),
Interpolation Search directly “guesses” index 6, where the value 70 is found.

💡 Real-Life Analogy

Think of it like searching for a word in a dictionary:
If you’re looking for a word starting with “T”, you’ll naturally open the book closer to the end rather than halfway through.
Your brain intuitively estimates the position — that’s interpolation in action!

⚙️ Time Complexity

Case	Time Complexity	Explanation
Best Case	O(1)	When the guessed position is exactly right.
Average Case	O(log log n)	Much faster than binary search for uniform data.
Worst Case	O(n)	When the data is not evenly distributed.

🧾 Key Points to Remember

Works only on sorted and uniformly distributed data.
Uses value-based position estimation, not middle-splitting.
Faster than Binary Search only when the data is evenly spaced.
Not suitable for data with clustering or uneven gaps.

🧠 Quick Recap

Feature	Binary Search	Interpolation Search
Split Method	Middle of array	Estimated position
Best Used For	Any sorted data	Uniformly distributed sorted data
Speed	O(log n)	O(log log n) (faster)
Example	Guess middle number	Guess exact likely number