Skip to content

Binary Search

Problem

Given a sorted array of integers and a target value, return the index of the target if found, otherwise return -1.

Approach

Both iterative and recursive implementations. Maintain lo/hi bounds; compute mid = lo + (hi - lo) // 2 to avoid overflow.

Algorithm Flow

flowchart TD
    A["lo = 0, hi = n - 1"] --> B{"lo <= hi?"}
    B -- No --> C["return -1<br/>(not found)"]
    B -- Yes --> D["mid = lo + (hi - lo) // 2"]
    D --> E{"nums[mid] == target?"}
    E -- Yes --> F["return mid"]
    E -- No --> G{"nums[mid] < target?"}
    G -- Yes --> H["lo = mid + 1<br/>(search right half)"]
    G -- No --> I["hi = mid - 1<br/>(search left half)"]
    H --> B
    I --> B

    style A fill:#7c3aed,color:#fff
    style F fill:#059669,color:#fff
    style C fill:#dc2626,color:#fff

When to Use

Sorted array lookup or any monotonic predicate search — "find target", "first/last occurrence", "search insert position". Foundation for bisect-based optimizations. Aviation: altitude/waypoint lookup tables.

Complexity
Time O(log n)
Space O(1) iterative, O(log n) recursive (call stack)

Implementation

Binary search.

Problem

Given a sorted array of integers and a target value, return the index of the target if found, otherwise return -1.

Approach

Both iterative and recursive implementations. Maintain lo/hi bounds; compute mid = lo + (hi - lo) // 2 to avoid overflow.

When to use

Sorted array lookup or any monotonic predicate search — "find target", "first/last occurrence", "search insert position". Foundation for bisect-based optimizations. Aviation: altitude/waypoint lookup tables.

Complexity

Time: O(log n) Space: O(1) iterative, O(log n) recursive (call stack)

binary_search(nums: Sequence[int], target: int) -> int

Return the index of target in sorted nums, or -1 if absent.

binary_search([1, 3, 5, 7, 9], 5) 2 binary_search([1, 3, 5, 7, 9], 4) -1 binary_search([], 1) -1

Source code in src/algo/searching/binary_search.py 
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
def binary_search(nums: Sequence[int], target: int) -> int:
    """Return the index of *target* in sorted *nums*, or -1 if absent.

    >>> binary_search([1, 3, 5, 7, 9], 5)
    2
    >>> binary_search([1, 3, 5, 7, 9], 4)
    -1
    >>> binary_search([], 1)
    -1
    """
    lo, hi = 0, len(nums) - 1

    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if nums[mid] == target:
            return mid
        if nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1

    return -1

binary_search_recursive 

binary_search_recursive(
    nums: Sequence[int], target: int
) -> int

Recursive binary search returning index or -1.

binary_search_recursive([2, 4, 6, 8, 10], 8) 3 binary_search_recursive([2, 4, 6, 8, 10], 5) -1

Source code in src/algo/searching/binary_search.py 
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
def binary_search_recursive(nums: Sequence[int], target: int) -> int:
    """Recursive binary search returning index or -1.

    >>> binary_search_recursive([2, 4, 6, 8, 10], 8)
    3
    >>> binary_search_recursive([2, 4, 6, 8, 10], 5)
    -1
    """

    def _helper(lo: int, hi: int) -> int:
        if lo > hi:
            return -1
        mid = lo + (hi - lo) // 2
        if nums[mid] == target:
            return mid
        if nums[mid] < target:
            return _helper(mid + 1, hi)
        return _helper(lo, mid - 1)

    return _helper(0, len(nums) - 1)
tests/searching/test_binary_search.py
"""Tests for binary search."""

from hypothesis import given
from hypothesis import strategies as st

from algo.searching.binary_search import binary_search, binary_search_recursive


class TestBinarySearch:
    def test_found_middle(self) -> None:
        assert binary_search([1, 3, 5, 7, 9], 5) == 2

    def test_found_first(self) -> None:
        assert binary_search([1, 3, 5, 7, 9], 1) == 0

    def test_found_last(self) -> None:
        assert binary_search([1, 3, 5, 7, 9], 9) == 4

    def test_not_found(self) -> None:
        assert binary_search([1, 3, 5, 7, 9], 4) == -1

    def test_empty_array(self) -> None:
        assert binary_search([], 1) == -1

    def test_single_element_found(self) -> None:
        assert binary_search([5], 5) == 0

    def test_single_element_not_found(self) -> None:
        assert binary_search([5], 3) == -1

    @given(
        data=st.lists(
            st.integers(min_value=-1000, max_value=1000),
            min_size=1,
            max_size=100,
            unique=True,
        ),
    )
    def test_finds_all_present_elements(self, data: list[int]) -> None:
        """Every element in the sorted array should be found."""
        data.sort()
        for i, val in enumerate(data):
            assert binary_search(data, val) == i


class TestBinarySearchRecursive:
    def test_found(self) -> None:
        assert binary_search_recursive([2, 4, 6, 8, 10], 8) == 3

    def test_not_found(self) -> None:
        assert binary_search_recursive([2, 4, 6, 8, 10], 5) == -1

    def test_empty(self) -> None:
        assert binary_search_recursive([], 1) == -1

    def test_single_element(self) -> None:
        assert binary_search_recursive([7], 7) == 0

    @given(
        data=st.lists(
            st.integers(min_value=-1000, max_value=1000),
            min_size=1,
            max_size=100,
            unique=True,
        ),
    )
    def test_agrees_with_iterative(self, data: list[int]) -> None:
        """Recursive and iterative must return the same result."""
        data.sort()
        target = data[0]
        assert binary_search_recursive(data, target) == binary_search(data, target)

Implement it yourself

Run: just challenge searching binary_search

Then implement the functions to make all tests pass. Use just study searching for watch mode.

Reveal Solution

Binary search.

Problem

Given a sorted array of integers and a target value, return the index of the target if found, otherwise return -1.

Approach

Both iterative and recursive implementations. Maintain lo/hi bounds; compute mid = lo + (hi - lo) // 2 to avoid overflow.

When to use

Sorted array lookup or any monotonic predicate search — "find target", "first/last occurrence", "search insert position". Foundation for bisect-based optimizations. Aviation: altitude/waypoint lookup tables.

Complexity

Time: O(log n) Space: O(1) iterative, O(log n) recursive (call stack)

binary_search(nums: Sequence[int], target: int) -> int

Return the index of target in sorted nums, or -1 if absent.

binary_search([1, 3, 5, 7, 9], 5) 2 binary_search([1, 3, 5, 7, 9], 4) -1 binary_search([], 1) -1

Source code in src/algo/searching/binary_search.py 
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
def binary_search(nums: Sequence[int], target: int) -> int:
    """Return the index of *target* in sorted *nums*, or -1 if absent.

    >>> binary_search([1, 3, 5, 7, 9], 5)
    2
    >>> binary_search([1, 3, 5, 7, 9], 4)
    -1
    >>> binary_search([], 1)
    -1
    """
    lo, hi = 0, len(nums) - 1

    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if nums[mid] == target:
            return mid
        if nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1

    return -1

binary_search_recursive 

binary_search_recursive(
    nums: Sequence[int], target: int
) -> int

Recursive binary search returning index or -1.

binary_search_recursive([2, 4, 6, 8, 10], 8) 3 binary_search_recursive([2, 4, 6, 8, 10], 5) -1

Source code in src/algo/searching/binary_search.py 
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
def binary_search_recursive(nums: Sequence[int], target: int) -> int:
    """Recursive binary search returning index or -1.

    >>> binary_search_recursive([2, 4, 6, 8, 10], 8)
    3
    >>> binary_search_recursive([2, 4, 6, 8, 10], 5)
    -1
    """

    def _helper(lo: int, hi: int) -> int:
        if lo > hi:
            return -1
        mid = lo + (hi - lo) // 2
        if nums[mid] == target:
            return mid
        if nums[mid] < target:
            return _helper(mid + 1, hi)
        return _helper(lo, mid - 1)

    return _helper(0, len(nums) - 1)