Interpolation Search
An improved variant of binary search for uniformly distributed sorted arrays. Instead of always checking the middle element, it estimates the position of the target based on its value.
Visualization
Details
Analogy
Imagine searching for a name in a phone book. If you're looking for 'Smith', you don't open to the middle page. Instead, you estimate that 'S' is about 3/4 through the book and open there. Interpolation search does the same - it calculates where the target value should be based on the values at the boundaries.
Purpose
To search sorted arrays more efficiently than binary search when data is uniformly distributed. It uses the value of the target to estimate its likely position, similar to how humans search in a phone book (looking toward the end for 'Z' names).
Use Cases
Excellent for uniformly distributed sorted data like dictionaries, phone books, or numerical datasets. Used in database indexing when data distribution is known. Ideal for large datasets where the overhead of calculation is justified. Not recommended for non-uniform data as it can degrade to O(n) performance.
Algorithm Steps
function interpolationSearch(array, target):
low = 0, high = length(array) - 1
while low <= high and target >= array[low] and target <= array[high]:
if low == high:
if array[low] == target: return low
return -1
pos = low + ((target - array[low]) * (high - low)) / (array[high] - array[low])
if array[pos] == target:
return pos
if array[pos] < target:
low = pos + 1
else:
high = pos - 1
return -1
Explanation
What's Happening?
Initial sorted array: [10, 20, 30, 40, 50, 60, 70, 80, 90, 100]. Starting interpolation search with low = 0 and high = 9.
Code Implementation
def interpolation_search(arr, target):
low, high = 0, len(arr) - 1
while low <= high and target >= arr[low] and target <= arr[high]:
if low == high:
if arr[low] == target:
return low
return -1
pos = low + int(((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