Binary Search

Reader guide and study workflow · Complete course map

A sorted event log has times [2,4,4,9]. A query asks where time 4 begins, including where it should be inserted when absent. Scanning from the front is easy and costs O(n). Stopping at any equal element answers a different question: index 2 contains 4, but the required boundary is index 1.

The opportunity comes from order. If one inspected value is too small, every earlier value is too small too. If it qualifies, every later value qualifies too. One comparison can certify a whole region, which is why fewer inspections are possible.

Keep the facts outside the undecided interval

Let lo separate values already known to be too small from the undecided region, and hi separate that region from values known to qualify. Use [lo,hi) with initial lo=0 and hi=n. The answer is a boundary, so n is a valid result even though it is not a valid element index.

For [2,4,4,9], target 4:

Undecided interval	Midpoint evidence	Certified region after the update
[0,4)	nums[2]=4 qualifies	all indices at or after 2 qualify; hi=2
[0,2)	nums[1]=4 qualifies	hi=1
[0,1)	nums[0]=2 is too small	all indices through 0 are too small; lo=1

At lo=hi, the two certified regions meet. Returning 1 follows from their meanings; there is no additional equality test to invent.

lo=0; hi=n
while lo<hi:
    mid=lo+(hi-lo)/2
    if nums[mid]<target: lo=mid+1
    else: hi=mid
return lo

Why not lo=mid in the first branch? For an interval of length one, the floor midpoint equals lo and nothing changes. Each actual update must preserve the answer and decrease hi-lo. Correctness without progress still permits an infinite loop.

Change the question before changing an operator

An exact-match search may use inclusive endpoints and return immediately on equality. A first-occurrence search must retain equality and search farther left. An upper bound asks for the first value strictly greater than the target. Combining lower and upper boundaries gives an occurrence range; manufacturing target+1 is unnecessary and can overflow.

Matrix search transfers exact search only when row-major order is globally sorted. A coordinate formula does not create that order. A median search changes the objects being searched: candidates are cuts, and a candidate must satisfy a rank count plus cross-boundary ordering. Read the later partition derivation before trying to adapt the element-search loop.

Peaks require another proof entirely. On [1,4,2,3,1], the array is not monotone. Comparing neighboring values can still retain a region containing some peak. Distinct rotated arrays similarly reveal one sorted half at a time. The reusable skill is justifying a discard, not declaring every logarithmic loop a lower-bound search.

Transfer: derive a new boundary without adding one to the target

For [-6,-2,-2,3,8] and threshold -2, return the last index whose value is at most the threshold, or -1 if none exists. Define the predicate, decide which equal values may be discarded, and give the result for thresholds -7 and 8 too. Would a one-pass scan also be correct?

Model answer: search the complement boundary

Find the first value greater than threshold. Values <=threshold belong to the completed left region, so the midpoint branch uses nums[mid]<=threshold to advance lo. On equality, keep searching right. The requested last index is the resulting exclusive boundary minus one.

For threshold -2 the upper boundary is 3, so return 2. For -7 it is 0, so return -1. For 8 it is 5, so return 4. No threshold+1 is evaluated, so the rule also works at the maximum int. A scan is correct but takes O(n); binary search exploits the sortedness to certify whole discarded regions in O(log n).

Before choosing a search loop

Write what a candidate means (element, insertion boundary, peak, or cut), the interval convention, what remains possible inside it, what is already known outside it, and why each update progresses. If these facts are unavailable, a familiar-looking midpoint is not enough to justify binary search.

Prerequisites and readiness

Know sorted order, half-open and inclusive intervals, and a loop variant that decreases. Be able to distinguish searching for one exact value, a boundary, any local peak, and a valid partition.

Reasoning workshop: every discard needs a proof

Half-open lower bound is a partition of known facts

Finish a boundary trace on [-4,-1,-1,6] with absent target 0. Start [lo,hi)=[0,4). The first midpoint is index 2, whose -1 is too small, so lo becomes 3. Complete the loop, then change the target to -1 and identify both its lower and upper boundaries. Which update treats equality differently?

Model answer: join the certified regions

For target 0, the remaining interval is [3,4). Midpoint 3 contains 6, so hi becomes 3. Return 3: indices before it are below 0 and indices at/after it qualify, even though no value equals the target.

For target -1, lower bound is 1 and upper bound is 3, giving inclusive occurrence range [1,2]. Lower bound moves hi left on equality; upper bound moves lo right on equality. Both loops terminate by shrinking hi-lo, but their certified left regions differ: <target versus <=target.

Search for >target directly, not >=target+1, because target+1 can overflow at the maximum integer. Keep interval conventions visible: boundary searches use exclusive hi=len(nums), while the exact matrix search uses inclusive hi=len(nums)-1. The same midpoint calculation does not make their updates interchangeable.

Not every logarithmic search has one monotone array

Find Peak compares neighbors rather than searching sorted values. In [1,4,2,3,1], both indices 1 and 3 qualify. An ascending slope guarantees a peak somewhere to the right before a descent or the outside boundary; it does not claim all right-side values are larger. The invariant is existence of a peak in the retained interval, not a global false/true predicate over the original values.

A rotated array similarly needs a local classification. For [4,5,6,7,0,1,2], the half ending at 7 is sorted. Target 1 is outside its value range, so it belongs to the other half if present. Distinct values make this classification unambiguous. Finding the minimum uses a different comparison, midpoint versus right endpoint, and retains midpoint when it could itself be the minimum.

A virtual array needs real global order

Map flat index k to row k/n and column k%n, where n is the number of columns. This saves flattening allocation, but it is valid only if the row-major sequence is sorted. Matrix [[1,4],[2,5]] has sorted rows and columns yet produces unsorted row-major values [1,4,2,5]. It is not an input to this version of SearchMatrix.

The median is a rank partition

Choose i elements from the smaller array and j=ceil((m+n)/2)-i from the other. A valid cut requires the largest left-side value to be no greater than the smallest right-side value. Only two cross-boundary comparisons are needed because each array is already sorted. Missing boundaries must be handled as missing, not represented by a finite “infinity” that valid int values can exceed.

The search is over m+1 cuts, not over m elements. If m<=n, every i from 0 through m gives a legal j: leftCount>=m makes j nonnegative, and leftCount<=n makes j<=n. This is why choosing the smaller array simplifies both the proof and the boundary checks.

Now derive the direction, rather than memorizing it. If A[i-1]>B[j], a value taken from A is too large to precede a value left in B. Increasing i would only increase A's left boundary and decrease j, making B's right boundary no larger. Every cut at or to the right of i therefore fails; set hi=i-1. Conversely, if B[j-1]>A[i], decreasing i makes A's right boundary no larger and B's left boundary no smaller. Every cut at or to the left fails; set lo=i+1. These are monotone violations over cuts even though the two arrays contain separate value sequences.

Trace A=[1,2] and B=[3,4,5,6]. The left side needs three values:

Cut i in A	Cut j in B	Boundary evidence	Decision
1	2	B[j-1]=4 > A[i]=2	Move i right; too few A values are on the left.
2	1	A[i-1]=2 <= B[j]=4; A's right side is absent	Valid: left maximum is 3, right minimum is 4.

The median is 3.5. No A right boundary exists at i=2, so the comparison requiring it is vacuously satisfied. For a trace in the other direction, A=[5,6], B=[1,2,3,4] first tries i=1, j=2. Since 5>3, move left to i=0, j=3; the valid boundaries are again 3 and 4. Both boundary cuts are real answers, not error cases.

For an odd total, return the maximum existing left value. For an even total, return the mean of that value and the minimum existing right value. The supplied implementation avoids signed addition overflow and preserves cancellation before rounding to float64. Both arrays empty return 0 by this pack's API convention; that value is not a mathematical median. Searching the smaller array costs O(log(m+1)) iterations and O(1) auxiliary space, with a constant-time boundary case when m=0.

A boundary test is more informative than one happy path

For each loop, test an answer at the first and last position, absence before and after the data, a one-element interval, and any permitted duplicates. For peak and balanced-tree style tasks, validate the defining property rather than an arbitrary preferred output. Finally, show why the exact update shrinks: lo=mid can stall under floor midpoint, while lo=mid+1 cannot in a lower-bound search.

Reconstruction lab and answer key

Search Insert Position

For [1,3,3,7] and target 3, what is the insertion index? Why is returning the first equal midpoint insufficient?

Model answer

The index is 1, the first 3. An equal midpoint might be the second 3 and would not satisfy the lower-bound contract. Continue searching the left boundary by setting hi=mid.

Search a 2D Matrix

A virtual search inspects flat index 4 in a matrix with two rows and three columns. Give its coordinates. If both rows are sorted but the first ends at 10 and the second begins at 7, can that coordinate mapping justify the binary-search discard?

Model answer

Coordinates are (4/3,4%3)=(1,1). The mapping is valid, but it supplies no ordering proof: the row-major sequence decreases from 10 to 7. Binary search may discard a region only under global sorted order. Correct index arithmetic and correct input preconditions are independent obligations.

Find Peak Element

For [9,7,5,3], complete the slope-search intervals from [0,3]. What certifies an endpoint peak? Now permit equal adjacent values: would an all-equal array still guarantee a strict peak?

Model answer

Midpoint 1 has 7>5, so retain [0,1]; midpoint 0 has 9>7, so retain [0,0] and return 0. Its only actual neighbor is smaller and its outside neighbor is treated as negative infinity. With equal adjacent values, an all-equal array of length greater than one has no strict peak, so that changed contract invalidates the existence guarantee.

Search in Rotated Sorted Array

Compare [1,1,1,3,1] and [1,3,1,1,1] while searching for 3 with lo=0, hi=4, mid=2. Both have the same values at lo, mid, and hi. Can the comparison nums[lo]<=nums[mid] justify discarding the left half in both? Explain which original precondition supplied the missing evidence.

Model answer

At lo=0,hi=4,mid=2, equality classifies the left half as sorted and discards it because 3 is outside [1,1); this first step happens to retain 3. But on [1,3,1,1,1], the identical endpoint/midpoint comparison discards the left half containing 3. With distinct keys, a wrap cannot be hidden by equal values; duplicates remove that evidence. The supported exercise retains distinct inputs, so duplicate-aware search needs a revised proof and can degrade to linear work.

Find First and Last Position of Element in Sorted Array

A lower-bound search returns len(nums) for a missing target larger than every value. A learner immediately evaluates nums[left] to check equality. What guard order is required, and what changes when the input itself is empty?

Model answer

Check left==len(nums) before indexing, using short-circuit logic, and return [-1,-1] when it holds. On empty input, lower bound is also zero=len(nums); exactly the same guard avoids reading nums[0]. Only after proving left is an existing position may equality be checked and the upper boundary converted to an inclusive last index.

Find Minimum in Rotated Sorted Array

Change the promise to allow duplicates. On [2,2,2,0,1,2], midpoint and right endpoint are both 2. Why is the original hi=mid branch unsafe, and what can safely be discarded when equality supplies no direction?

Model answer

With lo=0,hi=5,mid=2, hi=2 would discard the actual minimum at index 3. Equality cannot identify which segment contains the pivot. Discarding only the right endpoint is safe: a matching midpoint value remains if that value is minimal. Repeated equalities can force one-position progress and O(n) work, so this is an extension with a changed complexity, not the distinct-input algorithm’s original proof.

Median of Two Sorted Arrays

A proposed odd-length median partition puts floor((m+n)/2) values on the left but still returns the maximum left value. Find its result on A=[0], B=[2,4], then repair the rank convention.

Model answer

The ordered partition with one left value has left [0], right [2,4], so returning the maximum left gives 0 instead of median 2. Either put ceil(3/2)=2 values on the left and return its maximum, or use a matching rule that reads the minimum right. Rank count and the chosen boundary must agree; this pack uses the first convention.

Problems in this module

• Search Insert Position
• Search a 2D Matrix
• Find Peak Element
• Search in Rotated Sorted Array
• Find First and Last Position of Element in Sorted Array
• Find Minimum in Rotated Sorted Array
• Median of Two Sorted Arrays

Interactive checkpoint

Open the Binary Search quiz. The questions use exact, objectively gradeable answers. Work the reasoning drills above before opening their model answers.

Earlier-edition deep links

These anchors preserve links to headings from the original files. They do not reinstate superseded explanations.

Learner experience: how to make this topic stick

The moves to recognize

How to practice without turning it into grind

Debugging instincts to build

A small way to make it memorable

Earlier-edition pattern links

The opening now derives the choices above before naming individual recipes. These headings preserve prior bookmarks.

Pattern A: Lower bound / insertion position

Continue with the current reasoning workshop.

Pattern B: Binary search on a virtual array

Continue with the current reasoning workshop.

Pattern C: Peak search by slope

Continue with the current reasoning workshop.

Pattern D: Rotated array decision

Continue with the current reasoning workshop.

Pattern E: First/last occurrence

Continue with the current reasoning workshop.

Pattern F: Partition by count (median of two arrays)

Continue with the current reasoning workshop.

When to use Binary Search (checklist)

Continue with the current reasoning workshop.

Common failures (checklist)

Continue with the current reasoning workshop.

Problem mapping

Continue with the current reasoning workshop.