Table of Contents

1. Binary Search & Python’s bisect module
   1. Introduction
   2. Why binary search?
   3. Naive implementation
   4. bisect_left — leftmost occurrence
   5. bisect_right — rightmost occurrence
   6. When to use which

Binary Search & Python’s bisect module

Introduction

Understanding the thought process behind bisect_left and bisect_right — when to use each and why.

Why binary search?

Linear search scans every element in O(n). Binary search exploits sorted order to reduce the run time to O(log n). That’s the difference between scanning a million records and needing at most 20 comparisons. It’s also the idea powering B-tree indexes in most databases.

Use binary search whenever your data is sorted and you need fast lookups, range queries, or insertion-point finding.

Naive implementation

The following is a classic “book” implementation of the algorithm which returns an index if found, -1 otherwise.

    def binary_search(xs, key):
        if not xs or key is None:
            return -1
        left, right = 0, len(xs) - 1
        while left <= right:
            mid = (left + right) // 2
            if xs[mid] == key:
                return mid
            elif xs[mid] < key:
                left = mid + 1
            else:
                right = mid - 1
        return -1

    xs = [1, 2, 3, 4, 5]
    assert binary_search(xs, 7) == -1
    assert binary_search(xs, 5) == 4
    assert binary_search(xs, 1) == 0

This returns some index when a match is found. That’s fine for unique elements, but falls apart with duplicates. Enter bisect module included in the Python Standard library.

bisect_left — leftmost occurrence

Invariants

• Returns position i such that a[:i] < key and a[i:] >= key
• If key is present, i points to its leftmost copy
• Return range: [0, len(a)] — can return an index past the end

Implementation

    from bisect import bisect_left

    def left_most_search(a, key):
        i = bisect_left(a, key)
        if i >= len(a) or a[i] != key:  # bounds check first!
            return -1
        return i

    xs = [1, 2, 2, 2, 3, 4, 5]
    assert left_most_search(xs, 2) == 1
    assert left_most_search(xs, 3) == 4
    assert left_most_search(xs, 9) == -1

bisect_right — rightmost occurrence

Invariants

• Returns position i such that a[:i] <= key and a[i:] > key
• Never points to the key itself — always one position after it
• Return range: [0, len(a)]

Implementation

    from bisect import bisect_right

    def right_most_search(a, key):
        i = bisect_right(a, key)
        if i == 0 or a[i - 1] != key:
            return -1
        return i - 1

    xs = [1, 2, 2, 2, 3, 4, 5]
    assert right_most_search(xs, 2) == 3
    assert right_most_search(xs, 1) == 0
    assert right_most_search(xs, 9) == -1

When to use which

bisect_left

• Finding the first occurrence of a value
• Insertion point that preserves order, placing equal keys to the left
• Counting elements strictly less than a value: bisect_left(xs, key) gives the count

bisect_right

• Finding the last occurrence of a value
• Insertion point that places equal keys to the right
• Counting elements less than or equal to a value: bisect_right(xs, key) gives the count