Binary Search and the bisect Module

Updated

October 31, 2026

Binary Search and the bisect Module

Binary search locates elements in a sorted collection by repeatedly dividing the search space in half, finding targets in \(O(\log n)\) time. Selection algorithms like Quickselect find the \(k\)-th smallest element (such as the median or 95th percentile) in \(O(n)\) average time without sorting the full dataset. In Python, the boring default for binary search is the standard library’s C-accelerated bisect module.

Mental model

Binary Search Halving

Scanning 1,000,000 items linearly checks up to 1,000,000 elements. Binary search finds the target in at most 20 comparisons (\(\log_2 1000000 \approx 20\)):

Target: 38
[ 10, 14, 19, 26, 31, 38, 42, 55, 70 ]  Mid = idx 4 (31). 38 > 31 -> Search Right
                      [ 38, 42, 55, 70 ]  Mid = idx 6 (42). 38 < 42 -> Search Left
                      [ 38 ]              Mid = idx 5 (38). Match found!

The bisect Invariant

  • bisect_left(arr, x): Returns the leftmost insertion point for \(x\) to maintain sorted order. If \(x\) already exists, the returned index is before (to the left of) the existing entry.
  • bisect_right(arr, x): Returns the rightmost insertion point (after any existing entry).
Array:   [ 10,  20,  20,  20,  30 ]
Index:      0    1    2    3    4
                ^              ^
   bisect_left(20) = 1    bisect_right(20) = 4

Worked examples

Case 1: Binary Search from scratch

Save as binary_search_scratch.py. Implement iterative binary search with left/right insertion bounds.

# binary_search_scratch.py
def binary_search[T](items: list[T], target: T) -> int | None:
    low = 0
    high = len(items) - 1

    while low <= high:
        mid = (low + high) // 2
        if items[mid] == target:
            return mid
        elif items[mid] < target:
            low = mid + 1
        else:
            high = mid - 1

    return None


def lower_bound[T](items: list[T], target: T) -> int:
    low = 0
    high = len(items)

    while low < high:
        mid = (low + high) // 2
        if items[mid] < target:
            low = mid + 1
        else:
            high = mid

    return low


def main() -> None:
    order_ids = [102, 108, 115, 120, 120, 120, 135, 150]
    print(f"Sorted order IDs: {order_ids}")

    # Exact search
    target = 135
    pos = binary_search(order_ids, target)
    print(f"Exact match for {target}: index {pos}")

    # Lower bound for insertion
    first_120 = lower_bound(order_ids, 120)
    print(f"First occurrence of 120: index {first_120}")

    insert_125 = lower_bound(order_ids, 125)
    print(f"Slot to insert 125: index {insert_125}")


if __name__ == "__main__":
    main()

Run:

uv run python binary_search_scratch.py

Output:

Sorted order IDs: [102, 108, 115, 120, 120, 120, 135, 150]
Exact match for 135: index 6
First occurrence of 120: index 3
Slot to insert 125: index 6

Case 2: Production Range and Tier Queries with standard library bisect

Save as bisect_tiers.py. Categorize customer desk order totals into shipping tiers and perform range lookups using bisect.

# bisect_tiers.py
import bisect


def get_shipping_tier(order_total: float) -> str:
    # Cutoff thresholds
    cutoffs = [25.0, 50.0, 100.0]
    tiers = ["Standard ($8)", "Saver ($5)", "Express ($2)", "Free VIP"]
    idx = bisect.bisect_right(cutoffs, order_total)
    return tiers[idx]


def main() -> None:
    test_totals = [15.0, 25.0, 49.99, 50.0, 85.0, 150.0]
    print("Shipping Tier Classifications:")
    for total in test_totals:
        tier = get_shipping_tier(total)
        print(f"  Order ${total:6.2f} -> {tier}")

    # Maintaining a sorted stream of incoming ticket IDs
    ticket_stream = [100, 105, 110, 120]
    print(f"\nExisting stream: {ticket_stream}")
    print("Inserting 108 with bisect.insort...")
    bisect.insort(ticket_stream, 108)
    print(f"Updated stream:  {ticket_stream}")


if __name__ == "__main__":
    main()

Run:

uv run python bisect_tiers.py

Output:

Shipping Tier Classifications:
  Order $ 15.00 -> Standard ($8)
  Order $ 25.00 -> Saver ($5)
  Order $ 49.99 -> Saver ($5)
  Order $ 50.00 -> Express ($2)
  Order $ 85.00 -> Express ($2)
  Order $150.00 -> Free VIP

Existing stream: [100, 105, 110, 120]
Inserting 108 with bisect.insort...
Updated stream:  [100, 105, 108, 110, 120]

Case 3: Quickselect for Median Response Time

Save as quickselect_desk.py. Find the median ticket resolution latency without paying for a full \(O(n \log n)\) sort.

# quickselect_desk.py
import random


def quickselect[T](items: list[T], k: int) -> T:
    """Finds the k-th smallest element (0-indexed) in O(n) average time."""
    if not 0 <= k < len(items):
        raise IndexError("k out of range")

    low = 0
    high = len(items) - 1

    while low <= high:
        pivot_idx = _partition(items, low, high)
        if pivot_idx == k:
            return items[k]
        elif pivot_idx < k:
            low = pivot_idx + 1
        else:
            high = pivot_idx - 1

    return items[k]


def _partition[T](items: list[T], low: int, high: int) -> int:
    pivot = items[high]
    i = low
    for j in range(low, high):
        if items[j] < pivot:
            items[i], items[j] = items[j], items[i]
            i += 1
    items[i], items[high] = items[high], items[i]
    return i


def main() -> None:
    # Resolution latencies in seconds
    latencies = [320, 120, 450, 90, 600, 210, 180, 510, 290]
    print(f"Raw latencies: {latencies}")

    n = len(latencies)
    median_idx = n // 2

    # Quickselect modifies the list partially in place
    median_val = quickselect(latencies[:], median_idx)
    print(f"Median resolution latency (50th percentile): {median_val} seconds")


if __name__ == "__main__":
    main()

Run:

uv run python quickselect_desk.py

Output:

Raw latencies: [320, 120, 450, 90, 600, 210, 180, 510, 290]
Median resolution latency (50th percentile): 290 seconds

The trap

Calling bisect.bisect_left on an unsorted list fails silently without raising an error. It assumes the list is monotonic and performs binary search blindly, returning an arbitrary, nonsensical insertion index.

Always verify or guarantee that the collection is sorted prior to initiating binary search.

The boring rule

  1. Use Python’s built-in bisect module (bisect.bisect_left, bisect.bisect_right, bisect.insort) in production. It is implemented in C and runs in microseconds.
  2. If your collection is unsorted and you only search once, use a linear scan (target in my_list) or build a set. Sorting a list (\(O(n \log n)\)) just to search it once (\(O(\log n)\)) is slower than a single linear scan (\(O(n)\)).
  3. Use bisect when the collection is queried repeatedly over time.
  4. If you need percentiles or medians on massive collections, consider quickselect or Python’s statistics.median().

Try this

  1. Use bisect.bisect_left to implement an \(O(\log n)\) function that counts how many times a given number appears in a sorted list.
  2. Build an in-memory lookup table that maps numerical HTTP response codes (200, 404, 502) to category labels (Success, Client Error, Server Error) using bisect.bisect_right.