Picture a guessing game: someone picks a whole number from 1 to 100, and after each guess they only say "higher" or "lower," never the number itself. Guess 50. Told "higher," guess 75. Told "lower," guess 62. Keep splitting whatever range is left in half, and you land on the exact number within 7 guesses, out of 100 possibilities. That is binary search: throw away half of what is left at every single step. It looks simple on paper, but small mistakes in exactly where the two boundaries sit cause an infinite loop the moment you write it live. Get the pattern right once, and it stops being just "search a sorted array." It also handles rotated arrays, 2D grids, and "find the best possible answer" optimization problems.

Search space reduction

In the guessing game above, the answer to "is the number higher than my guess?" flips from true to false exactly once as your guesses climb from 1 to 100. That one-way flip is what let you throw away half the range with full confidence every time. The technical name for that shape is monotonic: false for a run of values, then true for the rest (or the other way around), with exactly one flip point in between. Binary search works whenever you can define a monotonic yes/no rule over the search space. At each step you check the rule at the midpoint and throw away the half that cannot contain the answer. That guarantees the remaining space halves every step, which is what gives O(log n): a range of 100 shrinks to 50, then 25, then 12, then 6, then 3, then 1, about 7 steps, not 100 one-by-one guesses.

lo + (hi - lo) // 2 instead of (lo + hi) // 2 is a habit worth keeping even in Python, where integers never overflow. It shows you understand why the naive version breaks in languages with fixed-width integers.

Remember: binary search needs a monotonic yes/no rule: false, then true, with one flip point. Halving only works because of that.

Finding boundaries (lower bound, upper bound)

Picture a shelf of 1,000 books sorted by page count, with several books tied at exactly 300 pages. You want the position of the first 300-page book on the shelf, not just whether one exists. Many real problems ask exactly that: not "does target exist" but "where would target go" or "what is the first or last position satisfying a condition." That is a boundary search, and it needs a variant template that never lets lo and hi cross too early:

The key differences from the exact-match template: hi starts at len(nums) (one past the end, meaning "not found, insert here"), the loop condition is lo < hi (not <=), and there is no early return, since the loop converges with lo == hi landing on the answer. Mixing one template's conventions with the other's is the number one source of infinite loops.

Remember: exact match uses lo <= hi and mid ± 1. Boundary search uses lo < hi and hi = mid. Never mix them.

Monotonic functions and searching the answer

Picture 10 packages that need to ship within 5 days on trucks of some capacity C. With C = 1, the trucks crawl and shipping takes 20 days: too slow. With C = 1000, everything fits on one truck and ships in 1 day: done. Somewhere between 1 and 1000, the answer to "can we finish within 5 days?" flips from no to yes and stays yes. "Search the answer" problems like this one are not phrased as array search at all, but they hide that same monotonic rule. Binary search over the answer space itself, capacities from 1 to the total weight, applying the boundary-search template to find the smallest C where the rule flips to true.

Recognizing this shape, a yes/no question that flips one-directionally as some parameter increases, is what separates candidates who only know "binary search on a sorted array" from those who can apply it broadly.

Remember: if a yes/no question flips exactly once as a parameter grows, you can binary search that parameter, even if there's no array in sight.

Binary Search

Binary Search (LeetCode 704)

Intuition: The baseline exact-match template. Confirm you can write it cold, with correct bounds, in under a minute.

Approach: Standard lo <= hi loop, compare the midpoint to target, narrow to the half that cannot contain it.

Complexity: Time O(log n), space O(1).

Common mistakes:

• Using hi = len(nums) together with lo <= hi (mixing template conventions): causes an out-of-range access at nums[hi] when hi == len(nums).
• Forgetting mid + 1 / mid - 1 and instead setting lo = mid / hi = mid, which can infinite-loop when lo and hi are adjacent.

Remember: the exact-match template narrows with mid + 1 / mid - 1, never plain mid.

Search in Rotated Sorted Array

Search in Rotated Sorted Array (LeetCode 33)

Intuition: The array is not fully sorted, but at any midpoint, at least one half (left-of-mid or mid-to-right) is guaranteed to be normally sorted. Figure out which half is sorted, then check whether the target lies in that half's range. If so, recurse there; if not, recurse into the other half.

Approach: Standard binary search loop, but before narrowing, check whether nums[lo..mid] is sorted by comparing nums[lo] and nums[mid].

Complexity: Time O(log n), space O(1).

Common mistakes:

• Using < instead of <= when checking nums[lo] <= nums[mid]. With only one element, or two equal boundary values, this misclassifies which half is sorted.
• Getting the boundary comparisons wrong (nums[lo] <= target < nums[mid]), missing a target that sits exactly at a boundary.

Remember: one half of a rotated array is always fully sorted. Find which one, then check if the target's range fits inside it.

Find Minimum in Rotated Sorted Array

Find Minimum in Rotated Sorted Array (LeetCode 153)

Intuition: The minimum is the rotation's "pivot point," the one place where nums[i] > nums[i+1]. Compare the midpoint to the rightmost element: if nums[mid] > nums[hi], the minimum must be to the right of mid, since the rotation point has not been passed yet. Otherwise it is at or to the left of mid.

Approach: A boundary-search style loop narrowing toward the pivot.

Complexity: Time O(log n), space O(1).

Common mistakes:

• Comparing nums[mid] to nums[lo] instead of nums[hi]. This breaks when the left half itself is the sorted, non-rotated portion.
• Using lo <= hi here instead of lo < hi. This template converges to a single index and does not need the equality case.

Remember: compare nums[mid] against nums[hi], not nums[lo], to find which side the rotation pivot is on.

Search a 2D Matrix

Search a 2D Matrix (LeetCode 74)

Intuition: If each row is sorted and the first element of each row is greater than the last element of the previous row, the whole matrix is really a single sorted 1D array wearing a 2D shape. You can binary search over the flattened index space and convert back to (row, col).

Approach: Binary search over indices 0 to rows*cols - 1, converting a flat index to (row, col) with divmod.

Complexity: Time O(log(rows·cols)), space O(1).

Common mistakes:

• Running two separate binary searches, one to find the row and one within it. Correct and still O(log n), but more code and more places to get bounds wrong than the flattened-index trick.
• Getting divmod(mid, cols) backwards (col, row instead of row, col).

Every problem in this lesson is one of two templates wearing a different costume: exact-match (lo <= hi, mid ± 1) or boundary-search (lo < hi, hi = mid on the "keep" branch). The rotated-array and matrix problems still narrow to an exact target, so they use the exact-match shape. Finding a boundary or a pivot uses the converging shape instead. Pick the template from what the problem asks (exact value vs. a boundary), then apply it mechanically. Most binary search bugs come from borrowing one template's loop condition with the other's update rule.

Remember: a sorted-rows matrix with each row starting above the previous row's end is one flat sorted array in disguise. Binary search the flat index.