📘 DSA Day 11 – Interpolation Search

📌 Introduction

Interpolation Search is an improved version of Binary Search that works on sorted and uniformly distributed arrays.
Instead of always picking the middle index, it estimates where the target value might be, based on its value relative to the first and last elements.

Think of it like looking for a name in a telephone book — if the name starts with “Z,” you don’t start in the middle, you jump near the end.

---

🔹 How It Works

1. Start with the low and high indices (low = 0, high = n-1).

2. Use the interpolation formula to estimate the probable position:

   

3. Check:

   • If arr[pos] equals target → found.

   • If arr[pos] is less than target → search right side (low = pos + 1).

   • If arr[pos] is greater than target → search left side (high = pos - 1).

4. Repeat until found or range becomes invalid.

---

📊 Example

Search for 33 in:
[10, 20, 30, 40, 50, 60, 70, 80, 90]

• Low = 0, High = 8

• Estimated position:

  

  Index 2 = 30 → less than 33 → shift low to 3.

• Repeat process → found at position 3.

---

💻 Pseudocode

function interpolationSearch(arr, target):
    low = 0
    high = length(arr) - 1

    while low <= high and target >= arr[low] and target <= arr[high]:
        pos = low + ((target - arr[low]) * (high - low)) / (arr[high] - arr[low])

        if arr[pos] == target:
            return pos
        if arr[pos] < target:
            low = pos + 1
        else:
            high = pos - 1

    return -1

---

💻 JavaScript Implementation

function interpolationSearch(arr, target) {
    let low = 0, high = arr.length - 1;

    while (low <= high && target >= arr[low] && target <= arr[high]) {
        if (low === high) {
            return arr[low] === target ? low : -1;
        }

        let pos = low + Math.floor(
            ((target - arr[low]) * (high - low)) / (arr[high] - arr[low])
        );

        if (arr[pos] === target) return pos;
        if (arr[pos] < target) low = pos + 1;
        else high = pos - 1;
    }

    return -1;
}

// Example usage
let arr = [10, 20, 30, 40, 50, 60, 70, 80, 90];
console.log(interpolationSearch(arr, 30)); // Output: 2

---

⚖ Time Complexity

• Best case: O(1)

• Average case: O(log log n) — faster than Binary Search for uniform data.

• Worst case: O(n) — if data is not uniformly distributed.

• Space Complexity: O(1)

---

📝 Key Points

• Works only for sorted data.

• Best performance on uniformly distributed data sets.

• Not great for skewed or clustered data.

---

✅ Tomorrow (Day 12) → We’ll cover Exponential Search.

#CodeWithGift #DSA2025 #JavaScript #DayEleven