Binary Search: Explained Visually

The idea: the dictionary trick

When you look up the word "neuron" in a printed dictionary, you do not start at page 1. You open it near the middle, see "lemon", and know neuron must be after it. You throw away the first half and repeat with the second half. In a few flips you are on the right page.

Binary search does exactly this with an array. It only works when the data is sorted (or, more generally, when you can always tell which half the answer is in).

Binary search, step by step

We keep two pointers, low and high, around the part of the array where the target could still be. At each step:

1. Find the middle: mid = (low + high) / 2 (rounded down).
2. If arr[mid] == target, we found it.
3. If arr[mid] < target, the target must be on the right, so set low = mid + 1.
4. If arr[mid] > target, the target must be on the left, so set high = mid − 1.
5. If low > high, the range is empty, so the target is not in the array.

Try it below. Pick a value that is present, then one that is missing, and step through.

Why binary search is so fast: O(log n)

Every check halves the remaining items: n → n/2 → n/4 → … → 1. The number of halvings needed to get from n down to 1 is log₂(n). Drag the slider to feel the difference:

Binary search code

Iterative binary search in Python

def binary_search(arr, target):
    low, high = 0, len(arr) - 1
    steps = 0
    while low <= high:
        mid = (low + high) // 2
        steps += 1
        if arr[mid] == target:
            return mid, steps
        elif arr[mid] < target:
            low = mid + 1          # target is in the right half
        else:
            high = mid - 1         # target is in the left half
    return -1, steps

arr = [3, 8, 12, 17, 21, 26, 31, 38, 44, 52, 57, 63, 70, 81, 95]
print(binary_search(arr, 57))
print(binary_search(arr, 40))

(10, 4)
(-1, 4)

57 is found at index 10 in 4 checks. 40 is not in the array, and binary search proves that in 4 checks too, while a linear search would need all 15.

The same code in other languages

static int binarySearch(int[] arr, int target) {
    int low = 0, high = arr.length - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;   // avoids integer overflow
        if (arr[mid] == target) return mid;
        if (arr[mid] < target) low = mid + 1;
        else high = mid - 1;
    }
    return -1;
}

int binarySearch(const vector<int>& arr, int target) {
    int low = 0, high = (int)arr.size() - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;   // avoids integer overflow
        if (arr[mid] == target) return mid;
        if (arr[mid] < target) low = mid + 1;
        else high = mid - 1;
    }
    return -1;
}
// The STL has it built in: std::binary_search, std::lower_bound, std::upper_bound

def binary_search_rec(arr, target, low, high):
    if low > high:
        return -1                                   # empty range: not found
    mid = (low + high) // 2
    if arr[mid] == target:
        return mid
    if arr[mid] < target:
        return binary_search_rec(arr, target, mid + 1, high)
    return binary_search_rec(arr, target, low, mid - 1)

Variations you must know

Plain binary search answers "is it there?". Most interview problems need a variation.

Lower bound: first position where value ≥ target

This version never stops early. It keeps shrinking until low == high, which is the first index whose value is greater than or equal to the target. With it you can find the first occurrence, the last occurrence, the count of a value, and where to insert a new value.

def lower_bound(arr, target):
    """First index whose value is >= target (where target would be inserted)."""
    low, high = 0, len(arr)          # note: high = len(arr), and low < high
    while low < high:
        mid = (low + high) // 2
        if arr[mid] < target:
            low = mid + 1
        else:
            high = mid
    return low

marks = [35, 42, 42, 42, 58, 67, 91]
first = lower_bound(marks, 42)
last = lower_bound(marks, 43) - 1
print("first 42 at", first, "| last 42 at", last, "| count =", last - first + 1)
print("insert 60 at index", lower_bound(marks, 60))

import bisect
print(bisect.bisect_left(marks, 42), bisect.bisect_right(marks, 42))

first 42 at 1 | last 42 at 3 | count = 3
insert 60 at index 5
1 4

Python's built-in bisect_left is exactly lower bound, and bisect_right gives the position just after the last equal value.

Binary search on the answer

This is the most powerful idea. Sometimes you are not searching an array at all. You are searching for the smallest (or largest) value that works, and you can check any candidate quickly. If "works" is monotonic (once a value works, every bigger value also works), you can binary search over the possible answers.

Problem (Koko eating bananas): there are piles of bananas, and Koko has h hours. Each hour she eats up to k bananas from one pile. What is the smallest speed k that lets her finish in time?

import math

def min_speed(piles, hours):
    """Smallest eating speed k so that all piles finish within `hours`."""
    def can_finish(k):
        return sum(math.ceil(p / k) for p in piles) <= hours

    low, high = 1, max(piles)
    while low < high:
        mid = (low + high) // 2
        if can_finish(mid):
            high = mid        # mid works, try slower
        else:
            low = mid + 1     # too slow, go faster
    return low

print(min_speed([3, 6, 7, 11], 8))
print(min_speed([30, 11, 23, 4, 20], 5))

4
30

The same pattern solves "minimum capacity to ship packages in D days", "split array largest sum", "square root of a number" and "aggressive cows".

Common bugs (and how to avoid them)

Where binary search is used in real life

• Database indexes (B-trees) use the same halving idea to find a row among millions.
• git bisect finds the commit that introduced a bug by testing the middle commit each time.
• Autocomplete finds the range of words starting with a prefix in a sorted list.
• Machine learning: searching for a good threshold or learning rate when the metric changes in one direction.
• Operating systems: finding free memory blocks and scheduling.