Binary Search

Overview

Binary Search is an efficient search algorithm that finds the position of a target value within a sorted array. The algorithm works by repeatedly dividing the search interval in half. If the value of the search key is less than the item in the middle of the interval, narrow the interval to the lower half. Otherwise, narrow it to the upper half. Repeatedly check until the value is found or the interval is empty.

The key requirement for binary search is that the data structure must be sorted. This allows the algorithm to eliminate half of the remaining elements at each step, making it significantly faster than linear search for large datasets. Binary search can be implemented both iteratively and recursively, with the iterative approach generally being preferred for its better space efficiency.

Binary search has a time complexity of O(log n), where n is the number of elements in the array. This logarithmic time complexity makes it extremely efficient for large datasets. The space complexity is O(1) for the iterative implementation and O(log n) for the recursive implementation due to the call stack.

The Ninety-Year Struggle to Get Binary Search Right

Binary search is deceptively simple. It sounds like a first-week algorithms exercise, you cut the array in half, decide which side the target is in, recurse. This apparent simplicity has misled generations of programmers into believing they can implement it correctly. They largely cannot.

The algorithm was first described in the computing literature by John Mauchly in 1946, and appeared in most early textbooks. The first published correct implementation, as measured by testing against edge cases, did not appear until 1962 (Peter Lawrence Weyer, in Communications of the ACM). Between 1946 and 1962, essentially every published binary search implementation contained a bug.

In a 1986 article titled "Programming Pearls: Writing Correct Programs," Jon Bentley described asking a class of professional programmers to write binary search on paper, and reported that only 10% got a correct implementation within two hours. Bentley's article notes that he had been using this exercise for years and consistently got the same result. The bugs varied: off-by-one errors in loop bounds, mishandled empty arrays, incorrect handling of the "not found" case, and (most seriously) integer overflow in the midpoint calculation.

The overflow bug is the famous one. Writing mid = (left + right) / 2 is arithmetically correct but computationally wrong: if left and right are both close to the maximum int value, their sum overflows to a negative number and the calculated midpoint is nonsense. The Java standard library's binary search had this bug for nine years, from Java 1.2 (1998) to Java 6 update 10 (2008), when Joshua Bloch published a blog post titled "Extra, Extra, Read All About It: Nearly All Binary Searches and Mergesorts are Broken" documenting the issue in Sun's JDK. The correct formulation is mid = left + (right - left) / 2, which is equivalent for non-overflowing values and safe for the boundary case.

The takeaway that most textbooks now include: getting binary search right is genuinely hard, and getting it right by writing it out on paper is even harder. Test carefully with n = 0, n = 1, target at position 0, target at position n−1, target not present, and target equal to duplicated elements.

Binary Search on the Answer

Binary search is not only a search algorithm, it is a general technique for solving optimisation problems by transforming them into decision problems. The pattern, called "binary search on the answer" (or sometimes "parametric search"), is one of the most powerful ideas in competitive programming and shows up constantly in interview questions.

The setup: you have a problem where you need to find the minimum (or maximum) value of some quantity subject to constraints. Directly computing the answer is hard, but for any candidate value X you can efficiently decide "does the constraint hold for this X?" If the answer to the decision question is monotone, true for all X above some threshold and false below, or vice versa, you can binary search for the threshold.

Example: minimum time to finish tasks on k machines. You have n tasks with given durations and k identical machines. What is the minimum time to finish all tasks? Direct computation is NP-hard. But for any candidate time T, you can check in O(n) whether it is possible to assign tasks to k machines so that every machine finishes by T, use a greedy fit. The answer is monotone: if T works, so does T+1. Binary search over T from 0 to sum(durations) gives the optimal time in O(n log(sum)).

Example: LeetCode 875, Koko eating bananas. Koko must eat all bananas from n piles in at most H hours, at some rate k bananas per hour. Find the minimum k. Direct computation is fiddly; the decision question "can Koko finish at rate k?" is straightforward (compute the total hours needed). Binary search over k from 1 to max(pile sizes).

Example: median of two sorted arrays (LeetCode 4). Direct computation requires O(m + n). Binary search on the partition point of the smaller array gives O(log min(m, n)). This is the "hard" interview problem that binary search on the answer makes tractable.

The pattern generalises to any problem with monotone predicates. Once you learn to spot it, you will see binary search on the answer everywhere: minimum-maximum problems, minimum-of-maximum problems, minimum-K-th-largest problems, allocation problems, and many geometric problems reduce to a small number of predicate evaluations combined with a logarithmic outer search.

The Modern Story: Cache-Friendliness and Branch Prediction

Classical binary search's O(log n) complexity looks unbeatable, but on modern hardware there are subtler considerations that change the practical picture.

The branch misprediction problem. Binary search's inner loop contains a conditional branch (if arr[mid] < target) that is fundamentally unpredictable, each iteration halves the search space, so half the time we go left and half the time we go right, and the CPU's branch predictor cannot do better than 50% accuracy. Every mispredicted branch on a modern out-of-order CPU costs 15–20 cycles of wasted work as the pipeline is flushed and refilled. For a binary search of a million elements (log₂ = 20 branches, roughly 10 mispredicted), that is ~200 cycles just in mispredictions.

Branchless binary search. Rewrite the algorithm using conditional moves instead of branches:

def branchless_search(arr, target):
    lo, n = 0, len(arr)
    while n > 1:
        half = n // 2
        lo = lo + half if arr[lo + half - 1] < target else lo
        n -= half
    return lo if lo < len(arr) and arr[lo] == target else -1

The conditional move is a single instruction and does not stall the pipeline. On integer arrays of moderate size, branchless binary search is 2–3x faster than the branchy version. This is why C++'s std::lower_bound and Rust's binary_search_by use branchless implementations internally.

The cache problem. Binary search on a large array is a disaster for cache: the first probe hits some element near the middle, then a quarter of the way in, then an eighth, and so on, every probe is likely a cache miss. On arrays that do not fit in L1 or L2 cache, binary search is memory-bandwidth-bound rather than CPU-bound.

Eytzinger layout. A cache-aware rearrangement of the sorted array where the elements are stored in the "breadth-first" order of the search tree: root at index 1, its children at 2 and 3, their children at 4, 5, 6, 7, and so on. This makes each level of the binary search consecutive in memory, which the cache prefetcher can accelerate. Paul-Virak Khuong and Pat Morin demonstrated in 2015 that Eytzinger-layout binary search is ~2x faster than standard binary search on large arrays, a real, measurable speedup on modern hardware for what is supposedly a solved problem.

SIMD-based search. On very small sorted arrays (up to about 16–64 elements), SIMD linear search with a comparison mask beats binary search entirely, because the branch misprediction cost dwarfs the O(log n) vs O(n) difference at small n. This is why production hash tables use linear probing for small buckets and only switch to more complex structures for larger ones.

How It Works

The algorithm works by:

Comparing the target with the middle element of the array
If they match, return the index
If the target is less than the middle element, search the left half
If the target is greater than the middle element, search the right half
Repeat until the element is found or the search space is exhausted

Algorithm Pseudocode


BinarySearch(arr, target):
    left = 0
    right = arr.length - 1
    
    while left <= right:
        mid = left + (right - left) // 2
        
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return -1  # Target not found

Implementation

Iterative Implementation


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

Recursive Implementation


def binary_search_recursive(arr, target, left, right):
    if left > right:
        return -1
    
    mid = left + (right - left) // 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)

Complexity Analysis

Time Complexity: O(log n) - Each step eliminates half the search space
Space Complexity: O(1) iterative, O(log n) recursive
Best Case: O(1) - Target at the middle
Worst Case: O(log n) - Target not found or at the edge

Common Trends in Problems where Binary Search is Applied

Sorted Arrays: Binary search requires sorted data, making it perfect for problems involving sorted arrays or when you can sort the data first.
Search Space Reduction: Problems where you need to eliminate half the search space at each step naturally fit binary search.
Boundary Finding: Binary search excels at finding boundaries, such as the first or last occurrence of an element, or insertion points.
Optimization Problems: When searching for a minimum or maximum value that satisfies certain conditions, binary search on the answer space is often the solution.
Monotonic Functions: Problems involving monotonic functions (always increasing or decreasing) can often be solved using binary search.

Binary Search Framework

Initialize left and right pointers to define the search space (typically 0 and n-1 for arrays).
Use a while loop that continues while left <= right (or left < right depending on the problem).
Calculate the middle index using left + (right - left) // 2 to avoid integer overflow.
Compare the middle element with the target and adjust the search space accordingly.
Handle edge cases carefully, especially when the target is not found or when dealing with duplicate values.

Search Variations

Finding First/Last Occurrence

When dealing with duplicate values, you might need to find the first or last occurrence of a target:


def find_first_occurrence(arr, target):
    left, right = 0, len(arr) - 1
    result = -1
    
    while left <= right:
        mid = left + (right - left) // 2
        if arr[mid] == target:
            result = mid
            right = mid - 1  # Continue searching left
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return result

Use the Standard Library

Before hand-writing any of these: Python's bisect module implements binary search in C and gets all the edge cases right. Reach for it first.

import bisect

i = bisect.bisect_left(arr, target)    # first index where arr[i] >= target
j = bisect.bisect_right(arr, target)   # first index where arr[i] >  target

found = i < len(arr) and arr[i] == target    # membership
count = j - i                                # number of occurrences of target
bisect.insort(arr, value)                    # insert, keeping the list sorted

# Python 3.10+ accepts a key, so you can search a list of objects directly:
i = bisect.bisect_left(records, target_date, key=lambda r: r.date)

bisect_left and bisect_right together replace most hand-written "find first / find last occurrence" code, including the function above.

Search in Rotated Array

Binary search can be adapted to work with rotated sorted arrays. The trick is that after any split, at least one half is still properly sorted, and you can test which one in O(1):


def search_rotated(arr, target):
    left, right = 0, len(arr) - 1
    
    while left <= right:
        mid = left + (right - left) // 2
        
        if arr[mid] == target:
            return mid
        
        # Left half is sorted
        if arr[left] <= arr[mid]:
            if arr[left] <= target < arr[mid]:
                right = mid - 1
            else:
                left = mid + 1
        # Right half is sorted
        else:
            if arr[mid] < target <= arr[right]:
                left = mid + 1
            else:
                right = mid - 1
    
    return -1

This version assumes distinct elements. With duplicates it breaks down: when arr[left] == arr[mid] you cannot tell which side is sorted, consider [3, 1, 3, 3, 3] versus [3, 3, 3, 1, 3], which look identical at the endpoints and midpoint. The usual patch is to shrink the window by one (left += 1) when the three values tie, which restores correctness but degrades the worst case to O(n). There is no way around that: with duplicates, the problem genuinely requires linear time in the worst case.

Common Pitfalls

Integer overflow. (left + right) // 2 can overflow in fixed-width languages when both indices are large. Use left + (right - left) // 2, as above. This was a genuine bug in the JDK's Arrays.binarySearch for nine years, and Jon Bentley noted that most binary searches in a published survey were subtly wrong.
Off-by-one in the loop condition. while left <= right with an inclusive right = len(arr) - 1, or while left < right with an exclusive right = len(arr). Mixing the two conventions causes infinite loops or missed elements. Pick one and hold it.
Infinite loops when narrowing. If a branch sets left = mid rather than mid + 1, and mid rounds down to left, the window stops shrinking. When you need left = mid, round the midpoint up: mid = left + (right - left + 1) // 2.
Requires random access. Binary search on a linked list is O(n), because reaching the midpoint costs O(n), the whole benefit is lost.
The array must actually be sorted. Binary search on unsorted data does not error; it silently returns wrong answers.

Related Search Techniques

Binary search on the answer. The most valuable generalisation. Whenever a predicate is monotonic, false, false, ..., false, true, true, ..., true, you can binary search for the boundary even when there is no array involved. "Find the minimum capacity that ships all packages within D days" is a binary search over capacities, not over an input list.
Exponential (galloping) search: for unbounded or very large ranges, double an index until you overshoot the target, then binary search the bracket you have found. O(log i) where i is the target's position, better than O(log n) when the target is near the front.
Interpolation search: instead of the midpoint, guess where the value should be by linear interpolation. O(log log n) on uniformly distributed data, but degrades to O(n) when the distribution is skewed.
Branchless / Eytzinger layout: a performance technique that stores the array in BFS order so that lookups become cache-friendly and can avoid unpredictable branches. Several times faster than textbook binary search on large arrays.

Related Algorithms

Explore other searching algorithms:

Linear Search - Simple O(n) search for unsorted data
Back to Searching Algorithms Overview