Binary Search

Binary search is the classic divide-and-conquer algorithm for finding a target value inside a sorted collection. Instead of checking every element one by one, it repeatedly cuts the remaining search space in half, so it can find an item among a billion sorted entries in about thirty comparisons instead of a billion. It shows up constantly in real code (database indexes, Python’s bisect module, git bisect) and in coding interviews, where subtle bugs in the loop bounds are the most common way candidates trip up.

Overview: How Binary Search Works

Think about looking up a word in a paper dictionary. You don’t start at page one and flip forward one page at a time — you open somewhere near the middle, check whether your word comes before or after that page, and throw away the half you don’t need. You repeat that on the remaining half, again and again, until you land on the page. That is exactly what binary search does to a sorted array.

Binary search keeps track of two boundaries, left and right, that mark the portion of the array still worth searching. On each step it looks at the element in the middle of that range:

• If the middle element equals the target, the search is done — return that index.
• If the middle element is smaller than the target, the target (if it exists) must be to the right, so the algorithm discards the left half by moving left just past the middle.
• If the middle element is larger than the target, the target must be to the left, so the algorithm discards the right half by moving right just before the middle.

The loop continues until either the target is found, or the boundaries cross (left becomes greater than right), which means the remaining search space is empty and the target is not present.

Why the array must be sorted

Binary search’s entire strategy depends on deciding, from a single comparison, which half of the array can be safely thrown away. That only works if the array is sorted: if the middle element is less than the target, every element to its left is guaranteed to also be less than the target, so none of them can possibly match. In an unsorted array that guarantee disappears — the target could be hiding anywhere — and binary search will silently return the wrong answer instead of raising an error. This is why binary search is almost always paired with a prior sort step, or used on data that is naturally sorted, such as a database index.

Time and Space Complexity

Every comparison in binary search throws away half of the remaining elements. Starting from n elements, after one comparison at most n / 2 remain, after two at most n / 4, and so on. The search ends once the remaining range shrinks to a single element, which happens after roughly log2(n) halvings. That is why binary search runs in O(log n) time: the number of comparisons grows logarithmically with the input size, not linearly. Doubling the size of the array only costs one extra comparison in the worst case.

Case	Time	Why
Best case	O(1)	The target happens to be at the very first middle index checked.
Average case	O(log n)	Each comparison halves the remaining search space, so the expected number of comparisons is proportional to log2(n).
Worst case	O(log n)	Even when the target is missing, the loop keeps halving the range until it is empty, which still takes at most about log2(n) + 1 comparisons.

Space complexity depends on which version you write. The iterative version (a while loop) only needs a fixed number of variables (left, right, mid), so it uses O(1) auxiliary space regardless of input size. The recursive version needs O(log n) space, because every recursive call adds a new frame to the call stack, and the recursion is exactly as deep as the number of halvings — roughly log2(n) frames — before it hits the base case.

Examples

Example 1: Basic iterative binary search

This is the standard implementation: shrink a [left, right] window until the target is found or the window is empty.

def binary_search(arr: list[int], target: int) -> int:
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

numbers = [2, 5, 8, 12, 16, 23, 38, 45, 56, 72, 91]
print(binary_search(numbers, 23))
print(binary_search(numbers, 100))

Output:

5
-1

The array has 11 elements at indices 0 through 10. Searching for 23: left = 0, right = 10, so mid = 5 and arr[5] is 23 — an immediate match, so the function returns 5. Searching for 100: the window keeps shrinking (mid takes the values 5, 8, 9, 10) and every middle value is smaller than 100, so left keeps climbing until it passes right, and the function returns -1 because 100 is not in the array.

Example 2: Recursive binary search

The same logic can be written recursively, replacing the loop with a call that narrows the window on each step. This version searches a sorted list of strings.

def binary_search_recursive(arr: list[str], target: str, left: int, right: int) -> int:
    if left > right:
        return -1
    mid = (left + right) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search_recursive(arr, target, mid + 1, right)
    else:
        return binary_search_recursive(arr, target, left, mid - 1)

words = ["apple", "banana", "cherry", "date", "fig", "grape", "kiwi"]
result = binary_search_recursive(words, "fig", 0, len(words) - 1)
print(result)
print(words[result])

Output:

4
fig

The list has 7 words at indices 0 through 6. First call: left = 0, right = 6, mid = 3, and arr[3] is "date", which is alphabetically before "fig", so the function recurses into the right half with left = 4. Second call: left = 4, right = 6, mid = 5, and arr[5] is "grape", which is after "fig", so it recurses into the left half with right = 4. Third call: left = 4, right = 4, mid = 4, and arr[4] is "fig" — a match, so it returns index 4. Note that the base case (left > right) is checked first on every call, which is what stops the recursion when a target is not present.

Example 3: Finding the first occurrence among duplicates with bisect

Real sorted data often contains duplicate values, and interview questions frequently ask for the first (or last) index of a target rather than any index. Rolling your own loop for this is error-prone, so Python’s standard bisect module is the right tool: bisect_left returns the leftmost position where a value could be inserted to keep the list sorted.

from bisect import bisect_left

def first_occurrence(arr: list[int], target: int) -> int:
    index = bisect_left(arr, target)
    if index < len(arr) and arr[index] == target:
        return index
    return -1

scores = [1, 3, 3, 3, 5, 7, 9, 9, 12]
print(first_occurrence(scores, 3))
print(first_occurrence(scores, 9))
print(first_occurrence(scores, 4))

Output:

1
6
-1

bisect_left(scores, 3) returns 1, the first index whose value is not less than 3, and scores[1] really is 3, so the function returns 1 — the first of the three 3s. bisect_left(scores, 9) returns 6, and scores[6] is 9, so it returns 6. bisect_left(scores, 4) returns 4 (the position where 4 would need to be inserted, right before the 5), but scores[4] is 5, not 4, so the function correctly reports that 4 is not in the list by returning -1.

How It Works Step by Step

Trace binary_search(numbers, 45) on numbers = [2, 5, 8, 12, 16, 23, 38, 45, 56, 72, 91] (indices 0 through 10):

• Step 1: left = 0, right = 10, mid = 5. arr[5] is 23, which is less than 45, so left moves to 6.
• Step 2: left = 6, right = 10, mid = 8. arr[8] is 56, which is greater than 45, so right moves to 7.
• Step 3: left = 6, right = 7, mid = 6. arr[6] is 38, which is less than 45, so left moves to 7.
• Step 4: left = 7, right = 7, mid = 7. arr[7] is 45 — a match, so the function returns 7.

Notice the search space shrank from 11 elements to 5, to 2, to 1 — roughly halving each time, which is the whole reason binary search is fast.

Common Mistakes

Mistake 1: An off-by-one that causes an infinite loop

A very common bug is forgetting to move left past mid when narrowing the right half. If mid itself is not excluded, and the target keeps landing in the same half, the window never shrinks and the loop runs forever.

def broken_search(arr: list[int], target: int) -> int:
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid  # BUG: should be mid + 1
        else:
            right = mid - 1
    return -1

If the target is larger than every element, left keeps being reassigned to the same mid value over and over — mid never moves, left never passes right, and the function hangs forever instead of returning -1. The fix is the one-character change shown in Example 1: left = mid + 1, which guarantees the window strictly shrinks on every iteration.

Mistake 2: Running binary search on unsorted data

Because binary search trusts the sort order to decide which half to discard, running it on unsorted data doesn’t raise an error — it just silently returns the wrong answer.

def binary_search(arr: list[int], target: int) -> int:
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

unsorted = [8, 2, 12, 5, 23, 16]
print(binary_search(unsorted, 5))

Output:

-1

The value 5 is actually present at index 3, but the array is not sorted, so the function’s left/right narrowing throws away the wrong half and reports -1. Always confirm the data is sorted (or sort it first with sorted(), which costs O(n log n)) before reaching for binary search.

Best Practices

• Only use binary search on data that is sorted (or that you sort yourself first) — verify this assumption rather than assuming it.
• Prefer the iterative version for production code: it avoids call-stack overhead, and although the recursion depth here is only O(log n) and won’t hit Python’s recursion limit for any realistic array size, the loop version is simpler to reason about and debug.
• Reach for the standard library’s bisect module (bisect_left, bisect_right, insort) for common variants like first occurrence, last occurrence, or insertion point, instead of hand-rolling the boundary logic every time.
• Decide explicitly what you want when duplicates are present — any match, first match, and last match are different problems with different loop conditions.
• Recognize the binary search the answer pattern: whenever a problem asks you to minimize or maximize a value and you can write a yes/no check that is monotonic (true for all values below some threshold and false above it, or vice versa), you can binary search over that answer space instead of the array itself.
• If the array is small (roughly under a few dozen elements) or you only search it once, a simple linear scan is often just as fast in practice and easier to read — binary search earns its complexity on large or repeatedly-searched data.

Practice Exercises

• Last occurrence: Using the bisect module, write last_occurrence(arr, target) that returns the index of the last matching element in a sorted list with duplicates, or -1 if the target is absent. Hint: look at bisect_right instead of bisect_left. For arr = [1, 3, 3, 3, 5] and target = 3, the expected result is 3.
• Search in a rotated sorted array: A sorted array has been rotated at an unknown pivot, for example [15, 18, 2, 3, 6, 12] was originally [2, 3, 6, 12, 15, 18]. Write a function that still finds a target’s index in O(log n) time without first un-rotating the array. Hint: at every step, at least one half of the current window is guaranteed to be normally sorted — figure out which half, and whether the target could be in it.
• Binary search the answer: Write integer_sqrt(n) that returns the floor of the square root of a non-negative integer n without using math.sqrt, by binary searching over the range of possible answers. For n = 28, the expected result is 5, since 5 * 5 = 25 <= 28 < 36 = 6 * 6.

Summary

• Binary search finds a target in a sorted collection by repeatedly comparing against the middle element and discarding the half that cannot contain the target.
• Time complexity is O(log n) in the average and worst case, and O(1) in the best case, because each comparison halves the remaining search space.
• Space complexity is O(1) for the iterative version and O(log n) for the recursive version, due to call-stack depth.
• The array must be sorted first — binary search on unsorted data compiles and runs fine, but silently returns wrong answers.
• The classic off-by-one bug is forgetting mid + 1 (or mid - 1) when narrowing the window, which causes an infinite loop instead of a crash.
• Python’s bisect module (bisect_left, bisect_right, insort) already implements the common variants — use it instead of reimplementing boundary logic by hand.
• Beyond array lookups, the same halving idea applies to binary search the answer problems whenever the search space is monotonic.