Lesson 15
Binary Search: Halve and Conquer
Find anything among a billion sorted items in about 30 guesses.
01Why it matters & the intuition
Binary search is the purest O(log n) algorithm and a pattern far beyond sorted arrays — 'binary search on the answer' solves scheduling, capacity and optimisation problems.
Think of it like…
The number-guessing game: 'I'm thinking of a number from 1 to 100.' Guess 50. 'Higher.' Guess 75. Each answer throws away half the remaining numbers.
02See it move
Press play, then step through slowly. Change the input and predict the next frame before you click.
- mid
- found
03Key ideas
Invariant
If the target exists, it is always inside [lo, hi]. Every step must shrink the range while keeping that promise.
Avoid overflow
Use lo + Math.floor((hi - lo) / 2). In languages with fixed-width ints, (lo + hi) / 2 can overflow.
Lower bound
The first index where arr[i] >= target — also the insertion point. Most off-by-one bugs disappear once you think in lower bounds.
Search the answer space
If a yes/no check is monotonic (false…false, true…true), binary search finds the boundary without any array at all.
04Build it from scratch
A clean reference implementation. Read it line by line — then close it and write your own in the lab below.
function binarySearch(arr: number[], target: number): number {
let lo = 0;
let hi = arr.length - 1;
while (lo <= hi) {
const mid = lo + Math.floor((hi - lo) / 2);
if (arr[mid] === target) return mid;
if (arr[mid] < target) lo = mid + 1; // discard left half
else hi = mid - 1; // discard right half
}
return -1;
}
// First index i with arr[i] >= target (arr.length if none).
function lowerBound(arr: number[], target: number): number {
let lo = 0;
let hi = arr.length; // half-open [lo, hi)
while (lo < hi) {
const mid = lo + Math.floor((hi - lo) / 2);
if (arr[mid] < target) lo = mid + 1;
else hi = mid;
}
return lo;
}05Complexity
| Operation | Time | Space |
|---|---|---|
| Search sorted array | O(log n) | O(1) |
| Lower / upper bound | O(log n) | — |
| Requires | sorted input (or monotonic predicate) | — |
06Check your understanding
07Code lab
Write Python(or switch to JavaScript) and run it against real test cases. Python runs inside your browser — nothing is uploaded — and a C++ reference solution is under “Solution”.
Search insert position
Write search_insert(nums, target) for a sorted array of distinct numbers. Return the index of target if found, otherwise the index where it would be inserted to keep order. Must be O(log n).