🌟(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 = 70Instead 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 |
About the Author
