Implementing Binary Search in Python Sequences

Hello! In the previous lesson, you kept a fixed-size window within valid boundaries as it moved across an array. Binary search also manages boundaries, but instead of visiting every position, it uses the order of a sorted sequence to rule out large groups of positions at once.

Today you’ll implement a search that returns a target’s index, or -1 if it is absent. The central challenge is not finding the midpoint; it is defining exactly which indices remain possible after each comparison. Getting that definition right prevents most off-by-one errors.

Turn sorted order into a smaller search interval

Suppose an ascending list has a middle value of 13 and you want 27. Neither 13 nor anything to its left can be the answer, so you can discard that entire portion. If the middle value is 32, you can instead discard it and everything to its right. This reasoning requires the sequence to be sorted in ascending order and its values to be comparable with the target.

Watch NeetCode’s Binary Search - Leetcode 704 - Python for the visual explanation and the Python loop. Pay particular attention to what happens when the two boundaries meet at one index: that position has not been checked yet.

We will use an inclusive interval: left and right are both indices that might still contain the target. Initially, they are 0 and len(nums) - 1. Once the target is found, return its index. Once left > right, no candidate indices remain, so return -1.

Trace the boundaries, including a missing step

The image below sketches a search for 27 in a ten-element sorted array. It captures the idea of discarding values, but its second comparison caption has the inequality backward: 27 < 32, not 27 > 32. It also skips a midpoint check of 16. Let’s make every comparison explicit.

With nums = [1, 5, 8, 10, 13, 16, 27, 32, 45, 60], choose the lower midpoint when an interval has two central positions:

Notice the third row. When the remaining candidates are at indices 5 and 6, checking index 5 does not justify jumping straight to a result. Its value, 16, must first be compared with 27; only then can index 5 be excluded.

This is a useful discipline for tracing binary search: record the interval before each check, and update a boundary only after accounting for the midpoint’s value.

Implement one consistent interval convention

Here is the complete iterative search. Its contract is: given an ascending sorted Python sequence with constant-time indexing, return an index containing target, or -1 if none exists.

def binary_search(nums, target):
    left = 0
    right = len(nums) - 1

    while left <= right:
        mid = (left + right) // 2

        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return -1

The loop’s governing idea is: if the target exists, its index is somewhere from left through right, inclusive.

• At the start, the whole sequence is eligible.
• If nums[mid] < target, sorted order rules out mid and every earlier index. The first possible index is mid + 1.
• If nums[mid] > target, sorted order rules out mid and every later index. The last possible index is mid - 1.

If there is a match, the function returns immediately. Otherwise, each iteration removes at least the checked midpoint. The interval therefore shrinks until it either finds the target or becomes empty. That explains both why the algorithm terminates and why -1 is correct when the loop ends.

Python’s // gives an integer index. For example, boundaries 5 and 6 produce midpoint 5. Python does not need a special midpoint formula to avoid integer overflow.

Where off-by-one errors appear

The condition left <= right is paired with inclusive boundaries. If left == right, exactly one candidate remains and the loop must check it. Replacing the condition with left < right would skip that candidate: searching [7] for 7 would incorrectly report failure.

The + 1 and - 1 are equally important. After checking a midpoint and finding a mismatch, that midpoint is no longer a candidate. If a search for 9 in [7] used left = mid instead of left = mid + 1, the boundaries would remain unchanged and the loop would repeat indefinitely.

An empty sequence works without a special case: right starts at -1, so left <= right is false and the function returns -1. No indexing occurs. These small cases are worth keeping beside the main example when checking an implementation:

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

The search also works when sorted values repeat, but this version returns any matching index, not necessarily the first or last. For example, searching [2, 4, 4, 4, 8] for 4 may return whichever 4 it encounters at a midpoint. Keep that distinction clear when reading a problem’s required output.

Cost and when to use it

Each unsuccessful comparison discards roughly half the remaining candidates. A list of about a million elements therefore needs only about twenty midpoint checks in the worst case. For a sorted Python list or tuple, this implementation takes $O(\log n)$ time and $O(1)$ auxiliary space: it stores a few indices and creates no sublists.

That bound assumes the data is already sorted and supports constant-time indexing. Sorting an unsorted list just to perform one search has its own cost; binary search does not make that preparation free. It is most useful when sorted order is given or maintained, particularly when many searches will use the same sequence.

Key takeaways

For this implementation, treat [left, right] as an inclusive set of possible indices. Check while left <= right; after a mismatch, exclude the checked midpoint with mid + 1 or mid - 1. A found value returns its index, while an empty interval returns -1. Testing empty inputs, one-element inputs, endpoints, and missing values helps expose boundary mistakes quickly.

Next, you’ll move from sorted-array boundaries to a stack, using it to keep track of opening delimiters while validating nested brackets.