Binary Search Implementation — Core Concepts

Why binary search matters

Linear search — scanning every element one by one — is O(n). Binary search is O(log n). For a list of one million items, that is the difference between 1,000,000 comparisons and about 20. This gap grows dramatically with data size, making binary search one of the most important patterns in programming.

The catch: binary search requires sorted data. If your data changes frequently and sorting is expensive, you need to weigh the cost. But for read-heavy workloads on sorted collections, binary search is unbeatable.

How it works

1. Start with two pointers: low at the beginning, high at the end.
2. Calculate the middle index: mid = (low + high) // 2.
3. Compare the middle element to your target.
4. If it matches, you found it.
5. If the target is smaller, move high to mid - 1 (search the left half).
6. If the target is larger, move low to mid + 1 (search the right half).
7. Repeat until low > high (target not found).

Each step eliminates half the remaining elements, giving logarithmic performance.

Python’s bisect module

Python ships with the bisect module, which implements binary search in C for maximum speed:

• bisect.bisect_left(a, x) — returns the leftmost position where x can be inserted to keep a sorted. If x exists, it returns the index of the first occurrence.
• bisect.bisect_right(a, x) — returns the position after any existing entries of x.
• bisect.insort_left(a, x) — inserts x into a in sorted order (left side).
• bisect.insort_right(a, x) — inserts x into a in sorted order (right side).

To check if a value exists in a sorted list:

import bisect

def binary_search(sorted_list, target):
    idx = bisect.bisect_left(sorted_list, target)
    if idx < len(sorted_list) and sorted_list[idx] == target:
        return idx
    return -1

Iterative vs. recursive

The iterative version is preferred in Python because it avoids recursion depth limits and function call overhead:

Iterative:

def binary_search_iterative(arr, target):
    low, high = 0, len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

Recursive:

def binary_search_recursive(arr, target, low=0, high=None):
    if high is None:
        high = len(arr) - 1
    if low > high:
        return -1
    mid = (low + high) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search_recursive(arr, target, mid + 1, high)
    else:
        return binary_search_recursive(arr, target, low, mid - 1)

For lists larger than about 1,000 elements, the recursive version risks hitting Python’s default recursion limit (1,000 frames).

Common variations

• Find first occurrence — use bisect_left and verify the element matches.
• Find last occurrence — use bisect_right and check the element at index - 1.
• Search in rotated sorted array — a modified binary search that first determines which half is properly sorted.
• Search on answer — binary search over possible answers (e.g., “what is the minimum speed to finish within time T?”).

Common misconception

“Binary search only works on numbers.” Binary search works on any sortable data — strings, dates, tuples, custom objects with comparison methods. The only requirement is that the collection is sorted by the same criteria you are searching on.

One thing to remember: Reach for bisect before writing binary search by hand. It is correct, fast (C implementation), and handles edge cases that trip up manual implementations.