You are given a list nums sorted from smallest to largest, and a number target. Return the position of target in the list, or −1 if it is not there. Your solution must run in O(\log n) time.
You have done this with a paper dictionary. To find "mango", you do not read every page from the start. You open it near the middle. If you land on "pear", "mango" comes earlier, so you ignore the back half and open the front half near its middle. Each look throws away half of what is left.
That is binary search. "Binary" means "in two parts": every step splits the remaining range in two and keeps one part.
So the real question is not what to do. It is how to write the boundaries so the search never misses the answer and never loops forever. The idea is easy. The boundaries are where every bug lives, and every later problem in this chapter depends on getting them right without hesitating.
Keep two markers, low and high, around the part of the list that could still hold the target. Then repeat:
Look at the number in the middle of that range.
If it is the target, you are done.
If it is smaller than the target, the target can only be to its right. Move low to just past the middle.
If it is bigger, the target can only be to its left. Move high to just before the middle.
If the range becomes empty, the target is not there.
Each step halves the range. How many halvings until one number is left? That count is \log_2 n, read "log base 2 of n". For 1,000,000 numbers it is about 20, because 2^{20} is about a million. So 20 comparisons instead of a million.
(1) The range covers the whole list.low is the first position, and high is the last real position, len(nums) - 1. Both ends are included in the range.
(2) Keep going while the range has at least one number. Because both ends are included, a range where low == high still holds one number, and that number must be checked. So the condition is <=. With <, a one-number range would be skipped, and a target sitting exactly there would be missed.
(3) The middle position.low + (high - low) // 2 gives the same answer as (low + high) // 2. The first form is safer. In languages with fixed-size whole numbers, like Java and C++, low + high can be too big to store when both are near the limit. The sum then wraps round to a negative number, and the program crashes when it uses it as a position. This was a real bug in Java's own library, found in 2006 after sitting there for nine years. Python and JavaScript cannot overflow here, but write it the safe way anyway. It costs nothing, and interviewers watch for it.
The // means "divide and round down". In TypeScript, Math.floor does the rounding.
(4) Found it. Return the position.
(5) The middle is too small. The target, if present, is to the right. Move low to mid + 1. We skip past mid itself, because we have just checked it.
(6) The middle is too big. Move high to mid - 1, again skipping mid.
(7) The range is empty, so the target is not in the list.
Dividing and rounding down has a side effect. When the range has only two numbers, mid always lands on the left one. For low = 4, high = 5, mid = 4 + 1 // 2 = 4.
If any branch then set low = mid, low would stay at 4 forever, the range would never shrink, and the loop would never end. That is the classic binary-search hang. Lines (5) and (6) avoid it by always moving pastmid.
Time. Each turn of the loop at least halves the range: it goes from n to about n/2, then n/4, and so on. After k turns, about n / 2^k numbers are left. The loop stops when fewer than 1 is left, which happens when 2^k is bigger than n, so after about \log_2 n turns. Each turn does constant work. So the time is O(\log n).
Almost every binary search you will ever write is one of these two shapes. Knowing which one you are writing prevents most bugs.
Shape A: find an exact value. This page's code.
python
low, high = 0, len(a) - 1 # high is a real positionwhile low <= high: # a one-number range is still checked mid = low + (high - low) // 2 if a[mid] == target: return mid if a[mid] < target: low = mid + 1 else: high = mid - 1return -1
Shape B: find a boundary. Find the first position where some yes/no question becomes "yes". Almost every harder binary-search problem really wants this.
python
low, high = 0, len(a) # high is ONE PAST the endwhile low < high: # stop when the range is empty mid = low + (high - low) // 2 if condition(mid): high = mid # mid might be the answer, so keep it else: low = mid + 1 # mid is not the answer, so drop itreturn low # low == high, the first "yes" position
Here is a picture that helps. In shape A, you are looking inside boxes, so high is the last real box. In shape B, you are looking for a fence between boxes: the point where "no" turns into "yes". A row of n boxes has n + 1 possible fence positions, counting both ends, so high starts at len(a), one past the last box.
Shape B never returns −1, and never tests for equality. It always settles on a position. Notice that it can use high = mid, because the loop is low < high. When the range has two numbers, mid is the left one, and high = mid shrinks the range to one number, which ends the loop. Only low = mid would hang.
Binary search does not actually need a list. It needs a monotonic yes/no question. Monotonic means the answer only changes once: it is "no, no, no, … , no", then "yes, yes, … , yes", and never goes back to "no".
"Is a[i] at least the target?" is such a question. So is "can Koko finish the bananas eating at speed s?" So is "is x × x at least n?" Whenever you can phrase a problem as "find the smallest value where this question turns to yes", you can binary search it, whether or not any list exists.
That is called binary search on the answer, and the rest of this chapter is built on it.
Search Insert Position. Shape B: return where the target would go.
First and Last Position of Element in Sorted Array. Two shape-B searches, one for each end of the run of equal values.
Python's bisect_left and bisect_right. Shape B, already written for you in the bisect module. Know what each returns: the first position whose value is at least the target, and the first position whose value is greater than the target.
"Why low + (high - low) // 2?" To avoid overflow in languages with fixed-size numbers. Mention the Java bug. It is a short, true story.
"Why <= and not <?" Because high is a real position, so a one-number range must still be checked. Then add that shape B uses <, because its high is one past the end.
"Where does an infinite loop come from?" Rounding down puts mid on low in a two-number range, so low = mid never moves.
"Can you write it recursively?" Yes. It uses O(\log n) memory for the calls, which is fine, but the loop is still preferred.
One thing to volunteer: say which of the two shapes you are writing before you write it. That one sentence prevents the boundary mistakes this problem exists to catch.