Binary Search

Halve the search space on every step: exact match, first and last position, rotated arrays and binary search on the answer, all in O(log n) checks.

Overview

Binary search finds a value, or a boundary, by looking at the middle of a range and throwing away the half that cannot hold the answer. Each step halves the range, so a million items need at most 20 checks and a billion need at most 30.

It does not need a sorted array as such. It needs a monotonic yes/no question: one that is 'no' for every candidate up to some point and 'yes' for every candidate after it. A sorted array gives you that question for free ('is this element at least the target?'), but so does 'can we ship all packages with capacity c?'.

Binary search is a test of precision. Most people know the idea. Fewer can say exactly what left and right mean, why the loop ends, and what is returned when the target is missing.

How many steps it takes

After k steps the range has about n / 2^k items left, so the search ends after about log2(n) steps.

1,000 — 1,000 checks — 10 checks
1,000,000 — 1,000,000 checks — 20 checks
1,000,000,000 — 1,000,000,000 checks — 30 checks

The binary search column is the smallest k with 2^k greater than n, which is ceil(log2(n + 1)).

Template 1: find an exact match

Use this when you want any index that holds the target, or -1. The range is closed: left and right are both still candidates, and the loop runs while the range is not empty (left = target (0 to n) | | With duplicates | any one of them | the first one |

To find the last occurrence, find the first index with a[i] > target and subtract one. That reuses the same template and avoids the infinite-loop trap of writing a second, upper-rounding version.

Binary search on the answer

Sometimes there is no array to search. The question asks for the smallest (or largest) value that makes something possible. If the check 'does value x work?' is monotonic, you can binary search the range of possible answers and run the check at each mid.

Koko Eating Bananas is the standard example: piles of bananas, h hours, one pile at a time, at most k bananas an hour. Find the smallest k that finishes in time. Any speed faster than a working speed also works, so the check is monotonic. Speed 1 is the lowest possible, and max(piles) always works because each pile then takes one hour (the problem guarantees h is at least the number of piles).

Trace for piles [3, 6, 7, 11], h = 8. The hours at speed k are the sum of ceil(pile / k).

1 — 1 — 11 — 6 — 1 + 1 + 2 + 2 = 6 — yes — hi = 6
2 — 1 — 6 — 3 — 1 + 2 + 3 + 4 = 10 — no — lo = 4
3 — 4 — 6 — 5 — 1 + 2 + 2 + 3 = 8 — yes — hi = 5
4 — 4 — 5 — 4 — 1 + 2 + 2 + 3 = 8 — yes — hi = 4
end — 4 — 4 — answer 4

The cost is O(n log M): log M steps over the answer range M, each running an O(n) check. The same shape solves Capacity To Ship Packages, Split Array Largest Sum and Minimum Days to Make m Bouquets. Aggressive Cows uses the mirror image: it wants the largest value that works, so the check is 'yes' up to a point and 'no' after it.

Rotated sorted arrays

A sorted array rotated at an unknown point, such as [4, 5, 6, 7, 0, 1, 2], is no longer sorted, but whenever you split it at mid, at least one half is sorted. Check which one, test whether the target lies inside it, and keep that half or the other.

1 — 0 — 6 — 3 — 7 — left (4..7) — no — left = 4
2 — 4 — 6 — 5 — 1 — left (0..1) — yes — right = 4
3 — 4 — 4 — 4 — 0 — found — return 4

This works when the values are distinct. With duplicates, a[left] == a[mid] == a[right] tells you nothing about which half is sorted; the usual fix is to shrink both ends by one, and the worst case becomes O(n).

Library functions

Know the library call, and be ready to write the loop yourself.

Python — bisect.bisect_left(a, x) — first i with a[i] >= x; the insertion point to the left of equal items
Python — bisect.bisect_right(a, x) — first i with a[i] > x; the insertion point to the right of equal items
Java — Arrays.binarySearch(a, key) — an index of key (no promise which one if there are duplicates), else -(insertion point) - 1

Python's bisect functions take a key argument since Python 3.10. Java's result is undefined if the array is not sorted.

What you will be able to do

Write exact-match and boundary binary search without off-by-one bugs, and state the invariant of each.
Find the first and last position of a value with one boundary function.
Recognize a 'smallest value that works' problem and binary search its answer range.
Search a rotated sorted array and explain why one half is always sorted.
Explain why mid = left + (right - left) / 2 matters in Java and C++.

When to use it

Searching a sorted array or a fully sorted matrix
Finding where a yes/no condition first becomes true
'Smallest or largest value that satisfies a condition' problems (binary search on the answer)
Rotated sorted arrays, mountain arrays and peak finding
The problem asks for O(log n) time on ordered data

More Coding & DSA topics

Start free on Cariara · Coding problems · System design studio