← Back to Algorithms

Interpolation Search

An improvement over binary search that works on uniformly distributed sorted arrays by making a position estimate based on the value being searched.

Algorithm Steps

How It Works

Key Steps:

1 Initialize the search by identifying the search space (the array to search in).
2 Compare the target value with the current element(s) being examined.
3 Based on the comparison, either:
  • Return the current position if the target is found
  • Continue searching in the appropriate portion of the array
4 Repeat steps 2-3 until either:
  • The target element is found
  • The entire search space has been examined
Time Complexity O(log log n)
Space Complexity O(1)