Binary Search

Binary search, the quintessential algorithm that opens new frontiers for searching. The funny thing about binary search is that you probably don't do it too often in real life. Dijkstra's algorithm almost reads like common sense — hey, we went down that road and it took longer, so don't go that way anymore. If I'm looking on a bookshelf I just kind of scan left to right looking for the book I need: good old linear search.

Let's do a little thought experiment. If I ask you to guess a number between 1 and 100 and you get three guesses, after each guess you get the information "higher" or "lower." Which is your best guess, and which is your worst guess? Well, if you guess 1 or 100, you've eliminated exactly 1 number by choosing that number. So unless you're trying to lose, don't choose that number. Now, 99 or 2 is a better choice because you eliminate 2 numbers — guess 99 and learn "lower," and you know the answer isn't 99 or anything above it. Starting to see a pattern? The best number to guess starting from the beginning is 50; after that it's halfway between, etc., etc. This is the intuition of binary search. If you've ever used a bisection method in numerical analysis it's strikingly similar. It also kind of reminds me of Zeno's paradox, except instead of halving a physical distance you're halving a range of numbers to converge on the target.

Algorithm

Let's actually play it out. Say the number is 81 (you don't know that yet — that's the whole point). You start with the range 1-100. Guess 50, the middle. "Higher." The range collapses to 51-100, exactly half what it was. Guess 75, the middle of what's left. "Higher" again. Down to 76-100, twenty-five numbers. Guess 88. "Lower." Down to 76-87, twelve numbers. Guess 81. Got it, in four guesses. On a bad day you'd take about seven — because ${\log }_2(100)\approx 6.6$, and "halve a hundred until you get to one" takes about that many rounds. That last sentence is the entire reason binary search has the runtime it does.

Given a sorted array $A$ and a target value $x$:

1. Compare $x$ with the middle element
2. If $x$ matches the middle element, return its index
3. If $x$ is greater than the middle element, search the right half
4. If $x$ is less than the middle element, search the left half
5. Repeat until the element is found or the search space is exhausted

Time Complexity

The "log" isn't magic — it's just what you get when you cut the size in half over and over. Start with $n$. After one step, $n/2$. After two, $n/4$. After three, $n/8$. After $k$ steps, $n/2^k$. You're done when that's down to one, which means $2^k=n$, which means $k={\log }_2(n)$. The exponent and the logarithm are inverses of each other, and that inverse relationship is where every $\log n$ in algorithm complexity ultimately comes from.

Implementation

def binary_search(arr, target):
    low = 0
    high = len(arr) - 1

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

    return -1  # Return -1 if the target is not found

# Example usage with a sorted array
arr = [12, 23, 34, 45, 56, 78, 89]
target = 56
result = binary_search(arr, target)

if result != -1:
    print("Element {} found at index {}.".format(target, result))
else:
    print("Element {} not found in the array.".format(target))

Edge cases that bite people

The implementation looks simple, but a few details have caused real outages. Worth knowing before you write one in an interview.

While this is not a math textbook, let's begin by examining pathological cases. The first flavor is integer overflow on fixed width. The problem is that you have two integers that are both fine, but their sum is sum-thing else — you know, the case where the sum doesn't actually give you the sum. In Java this manifests as a negative integer. In the proud tradition of numerical analysts we will find some way to add zero to this term in order to get the midpoint formula behaving correctly. Joshua Bloch wrote the following solution (see the Google Research blog post for the full archaeological dig):

int mid = low + (high - low) / 2;   // the "+ 0" that saves you

This is not really a problem in Python because there are no fixed widths, but for your own educational experience the pioneering minds at notesoncomputing.com have engineered a Python fixed-width simulator for your browser.

< vs <= in the loop. If you write while low <= high (the code above), you're doing exact-match binary search — return early when arr[mid] == target, return -1 if you fall out. If you write while low < high, you're doing a lower_bound variant — return low at the end, which is the insertion point where the target would go if it's missing. Both correct, just different algorithms. Mixing them up is the source of half the bugs in binary search.

The mid + 1 and mid - 1 updates are not optional. Once you've ruled out mid, you have to exclude it from the next range or the loop won't terminate. Setting low = mid instead of low = mid + 1 on the "greater than" branch is the classic infinite loop, and it only shows up when low and high become adjacent and mid == low. Pleasant.

What do you return when the target isn't there? Three conventions exist in the wild. Return -1 (simplest). Return the insertion point (more useful — tells the caller where to put the element). Or return -(insertion_point + 1) (Java's choice — distinguishes found from not-found while still encoding the position). Pick whichever the caller needs and document it. The version above uses the first.

Duplicates. If the array has multiple matching elements, standard binary search returns some matching index — possibly any of them, depending on the access pattern. If you need the leftmost or rightmost match specifically, you need a different variant: bisect_left and bisect_right in Python, lower_bound and upper_bound in C++.

Exercises

A full exercise set is available for this topic, structured as one worked example + 7 practice problems (across 7 surface contexts) + 2 pattern-resistant check problems.