Binary search in Python
Find a key in a sorted array. Compare the key with the middle item, and keep only the half that can hold the key.
- File
binary_search.py, 26 lines- Level
- Native tests
- pass in this build
- 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/binary-search/. The authors are listed in prov/2B7QDX.jsonl.
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 binary_search(a: Sequence[T], x: T) -> int:
"""Return an index i with a[i] == x, or -1 when x is not in a. The list a must be sorted."""
lo, hi = 0, len(a) # @line L1
while lo < hi: # @line L2
mid = lo + (hi - lo) // 2 # @line L3
if a[mid] < x: # @line L4
lo = mid + 1 # @line L5
elif x < a[mid]: # @line L6
hi = mid # @line L7
else:
return mid # @line L8
return -1 # @line L9
test_binary_search.py 43 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/binary-search/. The authors are listed in prov/2B7QDX.jsonl.
import random
from binary_search import binary_search
def test_examples() -> None:
a = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
assert binary_search(a, 23) == 5
assert binary_search(a, 2) == 0
assert binary_search(a, 91) == 9
assert binary_search(a, 30) == -1
assert binary_search(a, 1) == -1
assert binary_search(a, 100) == -1
def test_empty_and_single() -> None:
assert binary_search([], 1) == -1
assert binary_search([7], 7) == 0
assert binary_search([7], 3) == -1
def test_duplicates() -> None:
a = [1, 3, 3, 3, 5]
assert a[binary_search(a, 3)] == 3
def test_strings() -> None:
assert binary_search(["ant", "bee", "cat"], "bee") == 1
def test_random_against_linear_scan() -> None:
rng = random.Random(2150)
for _ in range(2000):
a = sorted(rng.randint(-20, 20) for _ in range(rng.randint(0, 30)))
x = rng.randint(-25, 25)
i = binary_search(a, x)
if x in a:
assert 0 <= i < len(a) and a[i] == x
else:
assert i == -1
What the next level needs
- I1 needs the shared cases of the contract and the JSON adapter (09.2), which are M0 work