Binary search is not really about sorted arrays. It is about a yes/no question whose answers, read left to right, look like no, no, no, yes, yes, yes. "Is nums[i] >= target?" on a sorted array has that shape. So does "is nums[i] > nums[i + 1]?" when looking for a peak, and "is nums[i] <= nums[last]?" on a rotated array. Once the question is monotone, probing the middle tells you which half cannot contain the boundary, and you discard it: n → n/2 → n/4 → … → 1 in ⌈log₂ n⌉ steps.

Interval problems use order differently. A set of ranges [start, end] can overlap in tangled ways, but once they are sorted by start, an interval can only overlap the ones immediately before it in that order. Sorting costs O(n log n); the sweep that follows is O(n).

There are many correct ways to write binary search and far more incorrect ones. The cure is to commit to a small number of templates, each with a stated invariant, and never mix their pieces.

Given a sorted array of distinct integers and a target, return the index of the target if present; otherwise return the index where it would be inserted to keep the array sorted. Must run in O(log n).

Brute force → optimal. Scanning left to right until nums[i] >= target is O(n). Because the predicate nums[i] >= target is false-then-true on a sorted array, binary search finds the switch point in O(log n). Using the half-open range [0, n) makes "insert at the end" (answer n) fall out naturally.

A peak is an element strictly greater than its neighbours; positions outside the array count as −∞. Adjacent elements are never equal. Return the index of any peak in O(log n).

Brute force → optimal. A linear scan for the first i with nums[i] > nums[i + 1] is O(n). The array is not sorted, but the predicate "slope goes down at i" has a guaranteed true somewhere in every uphill-ending range, which is all Template 2 needs. The array need not be monotone overall — we are not finding the maximum, only a peak.

A sorted array of distinct values was rotated at an unknown pivot, e.g. [0,1,2,4,5,6,7] became [4,5,6,7,0,1,2]. Return the minimum element in O(log n).

Brute force → optimal. A linear scan for the drop (or simply the min) is O(n). Comparing mid with hi — not with lo — gives a clean two-way split with no special case for the un-rotated array, because in a sorted array nums[mid] <= nums[hi] always and hi marches left to index 0.

An m × n matrix has every row sorted left to right and every column sorted top to bottom. Decide whether target is in it. (Variant LC 74 is stricter: each row also starts after the previous row ends, so the whole matrix is one sorted list.)

Brute force → optimal. Scanning every cell is O(m·n). Binary searching each row is O(m log n). The staircase walk is O(m + n), which is optimal for this matrix shape. For the LC 74 shape, treat index k in [0, m·n) as cell (k / n, k % n) and run one ordinary binary search: O(log(m·n)). The top-left corner does not work as a start — both neighbours are larger, so there is no decision.

Given sorted arrays a (length m) and b (length n), return the median of all m + n values. The required complexity is O(log(m + n)) — merging is not allowed.

Brute force → optimal. Merging both arrays and picking the middle is O(m + n) time and space; a two-pointer walk to the middle drops the space to O(1) but is still O(m + n). Binary searching i over the shorter array gives O(log min(m, n)). Searching the shorter array also guarantees j stays within [0, n]. Sentinels (Integer.MIN_VALUE / MAX_VALUE) stand in for "nothing on this side" when i or j is 0 or at the end.

Given an array of intervals [start, end] in any order, merge all overlapping intervals and return the non-overlapping intervals that cover exactly the same points. Intervals that touch ([1,4] and [4,5]) count as overlapping.

Brute force → optimal. Repeatedly scanning all pairs and merging any two that overlap until nothing changes is O(n²) per pass and up to O(n³) overall. Sorting first costs O(n log n) and makes the merge a single O(n) sweep — Template 3.

Given meeting times [start, end), decide whether one person can attend all of them. A meeting ending at 10 and one starting at 10 do not conflict. The natural follow-up (LC 253) asks for the minimum number of rooms so that every meeting can be held.

Brute force → optimal. Comparing every pair is O(n²). For the yes/no question, sorting and checking adjacent pairs is O(n log n): if any two meetings overlap, then in sorted order some adjacent pair overlaps. For the room count, push each meeting's end time onto a min-heap; before pushing, if the earliest-ending meeting has finished (peek() <= start), reuse its room by polling. The heap size at the end is the peak number of simultaneous meetings.

← 03 Strings & Sliding Window All drills 05 Linked Lists →