Interpolation Search is an advanced search algorithm that is particularly efficient in uniformly distributed, sorted arrays. Unlike binary search, which always divides the search space in half, interpolation search predicts the likely position of the search target based on the values at the boundaries. It effectively uses an estimation method to guess the position, making it faster in terms of the average search time complexity.

Understanding Interpolation Search

Interpolation Search works similarly to binary search, but instead of dividing the array into two equal parts, it uses a formula to find the probable position of the element. The key calculation here involves determining the "mid" or "probe" position more intelligently.

Key Concepts

1. Assumptions:
   • The array is sorted.
   • Ideally, the elements are uniformly distributed.
2. Time Complexity:
   • Average case: $O(\log(\log(n)))$.
   • Worst case: $O(n)$, which occurs when the elements are not distributed uniformly.
3. Formula:
   • The "mid" or "probe" position is estimated using: $$\text{probe} = \text{low} + \left(\frac{(x - \text{array}[\text{low}]) \times (\text{high} - \text{low})}{\text{array}[\text{high}] - \text{array}[\text{low}]}\right)$$
   Where:
   • `x` is the target value.
   • `low` and `high` are the current bounds on the array.

Working of Interpolation Search

Step-by-step Algorithm

1. Start with the current bounds as `low = 0` and `high = n-1`, where `n` is the size of the array.
2. If `x` is present, it should lie between `array[low]` and `array[high]`.
3. Calculate the "probe" position using the interpolation formula provided above.
4. Check:
   • If `array[probe] == x`, return the "probe" index.
   • If `array[probe] < x`, adjust `low` to `probe + 1`.
   • If `array[probe] > x`, adjust `high` to `probe - 1`.
5. Repeat steps 3-4 until `low <= high` and `array[low] <= x <= array[high]`.
6. If `x` is not found, return -1.

Example

Consider the sorted array:

• Financial data where the stock prices or indices are historical and tend to be uniformly distributed over short sessions.
• Real-world scenarios like looking up dictionary entries, where entries tend to have similarly structured lengths.
• Data with an uneven distribution or arrays with large discrepancies between the high and low values.
• Linked lists or other non-array data structures.