Interpolation Search

Implement a fast search for uniformly distributed sorted arrays using interpolation.

search sorted-array binary-search

Implement the function `interpolation_search(arr, target)` that performs **interpolation search** on a sorted list of integers `arr` (non-decreasing order). The function should return the index of `target` if present, or `-1` if absent.

Interpolation search works like binary search, but instead of always choosing the middle index, it estimates the likely position using a linear interpolation formula based on the target value and the values at the two ends. For a sorted array `arr` with indices `low` and `high`, the probe position is:

```
pos = low + ((target - arr[low]) * (high - low)) // (arr[high] - arr[low])
```

If `arr[high] == arr[low]`, you should fall back to checking `low` and `high` directly. If the target is less than `arr[low]` or greater than `arr[high]`, return `-1`. Otherwise, adjust the search range:
- If `arr[pos] == target`, return `pos`.
- If `arr[pos] < target`, search to the right: `low = pos + 1`.
- If `arr[pos] > target`, search to the left: `high = pos - 1`.

Continue until `low > high` or the range is invalid. The array may be empty.

You must not use Python's built-in `list.index` or `bisect` module. Implement the algorithm from scratch.

Constraints

- `arr` is a list of integers sorted in non-decreasing order.
- `len(arr)` can be 0 up to 10^5.
- Elements are integers that may be negative, zero, or positive.
- `target` is an integer.
- Time complexity: O(log log n) on average for uniformly distributed data; O(n) worst case.
- Space complexity: O(1) additional space.

Example

>>> interpolation_search([1, 2, 3, 4, 5], 3)
2
>>> interpolation_search([1, 2, 3, 4, 5], 4)
3
>>> interpolation_search([1, 2, 3, 4, 5], 6)
-1
>>> interpolation_search([], 5)
-1

25 points ~25 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Handle the empty array first: return -1.

Use the `while low <= high` loop with the formula for `pos`, but be careful of division by zero when `arr[high] == arr[low]`.

If the target is outside the current range `[arr[low], arr[high]]`, you can return -1 immediately.

When `arr[high] == arr[low]`, compare target with that value directly.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.