Master Binary Search: From Basics to Advanced Patterns

Binary search finds a value in a sorted array by checking the middle element and throwing away the half that cannot contain it, so a million sorted items take at most 20 checks.

The Basic Pattern

def binary_search(arr, target):
    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

The loop keeps one promise, called the invariant. If the target is in the array at all, it sits between left and right, both ends included. Each comparison either finds the target at mid or rules out mid and everything on one side of it, which is why the updates step past mid to mid + 1 or mid - 1.

Trace it on [2, 5, 8, 12, 16, 23, 38, 56, 72, 91] with target 23. The first middle is index 4, holding 16. That is too small, so left moves to 5. The next middle is index 7, holding 56, which is too big, so right moves to 6. The middle of 5 and 6 is index 5, and it holds 23.

Two small edits break it. With while left < right, a target left alone in a range of one element is reported missing. With left = mid in place of mid + 1, the loop can run forever, because once right is left or left + 1 the midpoint equals left and the range stops shrinking. In Java or C++, write the midpoint as left + (right - left) / 2, since a 32-bit left + right overflows on very large arrays.

Finding Boundaries

Often, you need to find the first or last occurrence.

def find_first(arr, target):
    left, right = 0, len(arr) - 1
    result = -1
    
    while left <= right:
        mid = (left + right) // 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

On a match, the function records the index and keeps looking left, since an earlier copy might exist. For the last occurrence, record the match and move left = mid + 1 instead. On [1, 3, 3, 3, 7] with target 3, the two versions return 1 and 3, so the count of 3s is their difference plus one.

The same shape finds the first index where any condition becomes true, as long as the condition is false for a stretch and then true for the rest. Record mid when the condition holds and search left, otherwise search right. The shipping problem at the end of this guide is exactly that.

Search in Rotated Array

A common variation is searching in a rotated sorted array, one that was sorted and then cut in two with the back piece moved to the front, like [4, 5, 6, 7, 0, 1, 2].

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

The array has one drop, where 7 falls to 0, and any range that avoids the drop is sorted. Splitting at mid puts the drop in at most one half, and nums[left] <= nums[mid] means the left half is the sorted one. Comparing the target with that half's two ends tells you whether to search it or the other half. Searching for 0, the first middle is 7, and 0 falls outside the sorted left half [4, 5, 6, 7], so the search moves right.

The <= in that check matters. When left and mid are the same index, which happens when the range has two elements, the left half is one element and counts as sorted. Change it to < and searching [3, 1] for 1 returns -1. The method also assumes distinct values. In [1, 0, 1, 1, 1] both ends and the middle are 1, so nothing tells you which half holds the drop. The usual fix moves both ends inward by one when that happens, which makes the worst case O(n).

Beyond Arrays

The same halving works on a range of values as well as on an array.

Say packages with weights [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] must ship in order within 5 days, and you want the smallest daily capacity that makes it. If some capacity is enough, every larger one is too. So "does capacity c finish in time?" is false for small values and true from some point on, which is the shape from the boundaries section.

def ship_within_days(weights, days):
    def fits(capacity):
        needed, load = 1, 0
        for w in weights:
            if load + w > capacity:
                needed += 1
                load = 0
            load += w
        return needed <= days

    left, right = max(weights), sum(weights)
    result = right
    while left <= right:
        mid = (left + right) // 2
        if fits(mid):
            result = mid
            right = mid - 1  # try smaller
        else:
            left = mid + 1
    return result

The range starts at the heaviest package, which has to fit on some day, and ends at the total weight, which ships everything on day one. Here it returns 15, and a capacity of 14 would need six days.

Recognizing It in a Problem

Look for sorted input, or a request for the smallest or largest value that passes a check you can run cheaply. Values up to about a billion are another hint, since a billion candidates take only about 30 halvings. Write the condition first and confirm it flips only once. Then test it on arrays of zero, one, and two elements, with targets below the smallest value and above the largest. For a routine to practice the boundary cases, see LeetCode interview tips.