Interpolation search in Python
Estimate the probe position by linear interpolation of the key between the endpoints; O(log log n) expected on uniform keys, O(n) worst case.
- File
interpolation_search.py, 27 lines- Level
- I0 not checked yet
- Toolchain
- Python 3.14, pytest 9
- Test framework
- pytest
- Run the tests
python3 -m pytest
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/interpolation-search/. The authors are listed in prov/XVAMYG.jsonl.
from collections.abc import Sequence
def interpolation_search(a: Sequence[float], x: float) -> int:
"""Return an index i with a[i] == x, or -1 when x is not in a.
The list a must hold numbers sorted in non-decreasing order. Each probe is
placed where x would be if the values in a[lo .. hi] grew in a straight
line. On keys drawn uniformly at random the expected number of probes is
about lg lg n; the worst case is n probes.
"""
lo, hi = 0, len(a) - 1 # @line L1
while lo <= hi and a[lo] <= x <= a[hi]: # @line L2
if a[lo] == a[hi]: # @line L3
return lo
pos = lo + int((x - a[lo]) * (hi - lo) // (a[hi] - a[lo])) # @line L4
pos = min(max(pos, lo), hi) # guard against rounding of float keys
if a[pos] < x: # @line L5
lo = pos + 1
elif a[pos] > x: # @line L6
hi = pos - 1
else: # @line L7
return pos
return -1 # @line L8
test_interpolation_search.py 76 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/interpolation-search/. The authors are listed in prov/XVAMYG.jsonl.
import random
from interpolation_search import interpolation_search
A = [10, 13, 18, 22, 27, 31, 38, 40, 47, 52, 56, 61, 67, 73, 78, 85, 90, 94]
def check(a: list[float], x: float) -> None:
r = interpolation_search(a, x)
if x in a:
assert 0 <= r < len(a) and a[r] == x
else:
assert r == -1
def test_example() -> None:
assert interpolation_search(A, 61) == 11
assert interpolation_search(A, 50) == -1
assert interpolation_search(A, 10) == 0
assert interpolation_search(A, 94) == 17
assert interpolation_search(A, 9) == -1
assert interpolation_search(A, 95) == -1
def test_edges() -> None:
assert interpolation_search([], 1) == -1
assert interpolation_search([4], 4) == 0
assert interpolation_search([4], 5) == -1
assert interpolation_search([4], 3) == -1
assert interpolation_search([5, 5, 5, 5], 5) == 0
assert interpolation_search([5, 5, 5, 5], 6) == -1
def test_bad_input_is_slow_but_correct() -> None:
a = list(range(999)) + [10**9]
assert interpolation_search(a, 998) == 998
assert interpolation_search(a, 10**9) == 999
assert interpolation_search(a, 999) == -1
def test_every_position_and_gap() -> None:
for n in range(0, 60):
a = [3 * i * i for i in range(n)]
for i in range(n):
assert interpolation_search(a, a[i]) == i
check(a, a[i] + 1)
check(a, a[i] - 1)
def test_duplicates() -> None:
rng = random.Random(77)
for _ in range(1000):
a = sorted(rng.randint(0, 6) for _ in range(rng.randint(0, 25)))
for x in range(-1, 8):
check(a, x)
def test_floats() -> None:
rng = random.Random(5)
for _ in range(300):
a = sorted(rng.random() for _ in range(rng.randint(1, 60)))
for v in a:
check(a, v)
check(a, rng.random())
check(a, -0.5)
check(a, 1.5)
def test_random_against_linear_scan() -> None:
rng = random.Random(1978)
for _ in range(3000):
a = sorted(rng.randint(-50, 50) for _ in range(rng.randint(0, 40)))
check(a, rng.randint(-55, 55))
What the next level needs
- the tests did not run in this build