Jump search in Python
Jump ahead by blocks of size about sqrt(n) to find the block that could hold the key, then scan that block linearly.
- File
jump_search.py, 33 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/jump-search/. The authors are listed in prov/FX08EH.jsonl.
import math
from collections.abc import Sequence
from typing import Protocol, TypeVar
class Ordered(Protocol):
def __lt__(self, other: "Ordered", /) -> bool: ...
T = TypeVar("T", bound=Ordered)
def jump_search(a: Sequence[T], x: T) -> int:
"""Return the smallest index i with a[i] == x, or -1 when x is not in a.
The list a must be sorted in non-decreasing order. The search jumps in
blocks of max(1, isqrt(n)) items, then scans one block, so it makes at most
ceil(n / m) + m comparisons, about 2 * sqrt(n), and uses O(1) extra space.
"""
n = len(a)
m = max(1, math.isqrt(n)) # @line L1
lo, hi = 0, min(m, n) # @line L2
while hi < n and a[hi - 1] < x: # @line L3
lo, hi = hi, min(hi + m, n) # @line L4
i = lo # @line L5
while i < hi and a[i] < x: # @line L6
i += 1 # @line L7
if i < n and a[i] == x: # @line L8
return i
return -1 # @line L9
test_jump_search.py 88 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/jump-search/. The authors are listed in prov/FX08EH.jsonl.
import bisect
import random
from jump_search import jump_search
A = [3, 8, 11, 15, 19, 23, 27, 31, 35, 40, 44, 50, 57, 62, 68, 71]
def test_example() -> None:
assert jump_search(A, 57) == 12
assert jump_search(A, 20) == -1
assert jump_search(A, 80) == -1
assert jump_search(A, 3) == 0
assert jump_search(A, 71) == 15
assert jump_search(A, 1) == -1
def test_edges() -> None:
assert jump_search([], 1) == -1
assert jump_search([4], 4) == 0
assert jump_search([4], 5) == -1
assert jump_search([4], 3) == -1
assert jump_search([2, 2, 2, 2, 2], 2) == 0
def test_first_occurrence_across_block_boundary() -> None:
# n = 9, m = 3: the copies of 5 start in the first block and fill the second.
a = [1, 2, 5, 5, 5, 5, 6, 7, 8]
assert jump_search(a, 5) == 2
a = [1, 2, 3, 5, 5, 5, 5, 7, 8]
assert jump_search(a, 5) == 3
def test_every_position_and_gap() -> None:
for n in range(0, 70):
a = list(range(0, 2 * n, 2))
for i in range(n):
assert jump_search(a, 2 * i) == i
for g in range(-1, 2 * n + 1, 2):
assert jump_search(a, g) == -1
def test_comparison_bound() -> None:
class Key:
count = 0
def __init__(self, v: int) -> None:
self.v = v
def __lt__(self, other: "Key") -> bool:
Key.count += 1
return self.v < other.v
def __eq__(self, other: object) -> bool:
Key.count += 1
return isinstance(other, Key) and self.v == other.v
for n in [1, 2, 5, 16, 100, 1000]:
a = [Key(2 * i) for i in range(n)]
m = max(1, int(n**0.5))
while m * m > n:
m -= 1
bound = -(-n // m) + m
worst = 0
for v in range(-1, 2 * n + 1):
Key.count = 0
jump_search(a, Key(v))
worst = max(worst, Key.count)
assert worst <= bound
if n == 16:
assert worst == 8
def test_random_against_bisect() -> None:
rng = random.Random(6021)
for _ in range(3000):
a = sorted(rng.randint(-15, 15) for _ in range(rng.randint(0, 40)))
x = rng.randint(-17, 17)
i = bisect.bisect_left(a, x)
want = i if i < len(a) and a[i] == x else -1
assert jump_search(a, x) == want
def test_strings() -> None:
assert jump_search(["ant", "bee", "cat", "dog", "eel"], "dog") == 3
What the next level needs
- the tests did not run in this build