Python Binary Search

Binary search is an efficient algorithm for finding a target value inside a sorted sequence. Instead of checking every element one by one like a linear search, it repeatedly cuts the search space in half, which makes it dramatically faster for large datasets. Understanding binary search is essential not only for coding interviews but also for using Python’s built-in bisect module effectively in real programs.

Overview / How It Works

Binary search works on the principle of divide and conquer. Given a sorted list, you compare the target value to the element in the middle of the list. If they match, you’re done. If the target is smaller than the middle element, you know it can only exist in the left half of the list, so you discard the right half entirely. If it’s larger, you discard the left half. You repeat this process on the remaining half until you either find the target or run out of elements to check.

This is why the list must be sorted before you can binary search it — the algorithm relies on being able to make a directional decision (“go left” or “go right”) based on a single comparison. On an unsorted list, that comparison tells you nothing useful.

Internally, a typical binary search implementation keeps track of two pointers, low and high, that mark the boundaries of the region still being searched. Each iteration computes a mid index between them, inspects sequence[mid], and narrows low or high accordingly. Because the search space is halved every step, binary search runs in O(log n) time, compared to O(n) for a linear scan. For a list of one million sorted items, linear search might need up to a million comparisons in the worst case, while binary search needs at most about twenty.

Python lists are backed by contiguous arrays (technically arrays of pointers to objects), so random access via indexing — sequence[mid] — is O(1). This is what makes binary search practical on lists: jumping straight to the middle element costs the same regardless of where mid is. This would not be true for a linked list, where reaching the middle element requires walking through it node by node.

Syntax

There’s no dedicated keyword for binary search in Python — you either write the loop yourself or use the standard library’s bisect module. The general shape of a manual implementation looks like this:

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

Part	Meaning
low, high	Indices marking the current search boundaries (inclusive on both ends)
mid	The midpoint index being checked this iteration
sequence[mid] == target	Success case — return the index where the value was found
sequence[mid] < target	Target must be to the right — discard the left half by moving low
else branch	Target must be to the left — discard the right half by moving high
return -1	Loop ended without finding the target — it isn’t present

Python’s standard library also offers the bisect module, which provides fast, battle-tested binary search utilities: bisect.bisect_left, bisect.bisect_right, and bisect.insort. These don’t just find a value — they find the correct insertion point to keep a list sorted.

Examples

Example 1: Basic Iterative Binary Search

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


numbers = [2, 5, 8, 12, 16, 23, 38, 45, 56, 72]
result = binary_search(numbers, 23)
print(f"Index of 23: {result}")

missing = binary_search(numbers, 24)
print(f"Index of 24: {missing}")

Output:
Index of 23: 5
Index of 24: -1

The function narrows the search window each time it fails to land on the target directly. Since 24 doesn’t exist in the list, low eventually crosses past high, the loop condition low <= high becomes false, and the function correctly reports failure with -1.

Example 2: Recursive Binary Search

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


words = ["apple", "banana", "cherry", "date", "fig", "grape", "kiwi"]
print(binary_search_recursive(words, "fig"))
print(binary_search_recursive(words, "mango"))

Output:
4
-1

This version expresses the same halving logic recursively instead of with a while loop. Each call either returns an answer or delegates to a smaller sub-problem. Note that this works on any sorted sequence supporting comparison and indexing, including a list of strings, since Python compares strings lexicographically.

Example 3: Using the bisect Module in Practice

import bisect

scores = [55, 62, 68, 74, 81, 89, 95]
grade_cutoffs = [60, 70, 80, 90]
grade_letters = ["F", "D", "C", "B", "A"]


def letter_grade(score):
    index = bisect.bisect_right(grade_cutoffs, score)
    return grade_letters[index]


for score in scores:
    print(f"{score} -> {letter_grade(score)}")

sorted_scores = [55, 62, 68, 74, 81]
bisect.insort(sorted_scores, 70)
print(sorted_scores)

Output:
55 -> F
62 -> D
68 -> D
74 -> C
81 -> B
89 -> B
95 -> A
[55, 62, 68, 70, 74, 81]

Here, bisect_right is used not to find an exact value, but to find how many cutoff values a score exceeds — a classic real-world use of binary search for classification. bisect.insort inserts 70 into sorted_scores at the correct position using binary search internally, keeping the list sorted without a separate sort call.

How It Works Step by Step

Trace binary_search([2, 5, 8, 12, 16, 23, 38, 45, 56, 72], 23):

• Start: low = 0, high = 9. mid = (0 + 9) // 2 = 4. sequence[4] = 16. Since 16 < 23, set low = 5.
• Next: low = 5, high = 9. mid = (5 + 9) // 2 = 7. sequence[7] = 45. Since 45 > 23, set high = 6.
• Next: low = 5, high = 6. mid = (5 + 6) // 2 = 5. sequence[5] = 23. Match found — return 5.

Notice the search space shrank from 10 elements to 5, then to 2, then to 1 — each step roughly halves the remaining candidates, which is exactly the logarithmic behavior that gives binary search its O(log n) complexity.

Common Mistakes

Mistake 1: Running binary search on an unsorted list. Binary search silently produces wrong results (not an error) if the input isn’t sorted, because the “go left or right” decision depends entirely on order. Always sort first, or maintain the list in sorted order as you build it:

# Wrong: list is not sorted
unsorted = [8, 3, 12, 5, 1]
# binary_search(unsorted, 5) may return -1 even though 5 is present

# Correct: sort before searching
sorted_list = sorted(unsorted)
index = binary_search(sorted_list, 5)

Mistake 2: Using mid = (low + high) / 2 instead of integer division. In Python 3, the / operator always returns a float, so sequence[mid] would raise a TypeError since list indices must be integers. Always use // for the floor division that produces a valid index:

# Wrong: produces a float index
mid = (low + high) / 2  # e.g. 4.5, not usable as a list index

# Correct: integer (floor) division
mid = (low + high) // 2

Mistake 3: Off-by-one errors in the boundary update. Forgetting to move low or high past mid (e.g. writing low = mid instead of low = mid + 1) can cause an infinite loop, because the search space never shrinks when the target isn’t at mid.

Best Practices

• Prefer the standard library’s bisect module for production code — it is implemented in C, well-tested, and handles edge cases correctly.
• Only binary search a list if you’ll query it multiple times; if you search once, a single linear scan is simpler and the sort cost isn’t worth paying.
• Use bisect_left when you need the leftmost insertion point (e.g. for duplicates or to detect exact membership), and bisect_right when you want to insert after existing equal elements.
• Keep your data sorted incrementally with bisect.insort rather than repeatedly calling sorted() after every insertion, which is far more expensive.
• Write the loop condition as low <= high, not low < high, unless you have a specific reason — using the wrong one is a common source of missed matches at the boundary.
• For custom objects, ensure they support the comparison operators (__lt__, __eq__) or extract a sort key so bisect functions can compare them meaningfully.

Practice Exercises

• Exercise 1: Write a function find_first_occurrence(sequence, target) that returns the index of the first occurrence of target in a sorted list that may contain duplicates (e.g. [1, 2, 2, 2, 3, 4] searching for 2 should return 1, not any of the other matching indices).
• Exercise 2: Using bisect.bisect_left, write a function that checks whether a value exists in a sorted list without doing a linear in check, and returns True/False.
• Exercise 3: Implement binary search for the “closest value” problem: given a sorted list and a target, return the value in the list that is numerically closest to the target (it may not be an exact match).

Summary

• Binary search finds a target in a sorted sequence by repeatedly halving the search space, running in O(log n) time versus O(n) for linear search.
• It relies on comparing the target to the middle element and discarding the half that cannot contain it.
• Manual implementations use low, high, and mid pointers, updated with integer (//) division.
• Python’s built-in bisect module (bisect_left, bisect_right, insort) provides fast, correct binary search utilities for real-world use.
• Binary search only works correctly on sorted data — running it on unsorted data gives silently wrong results, not an error.