Find the boundary before naming the loop

Sorted event times: [2,4,4,9]. Find the first position at least 4.

A midpoint sees the second 4. Decision: Which entire region is now certified, and why can’t equality return yet?

1 / 12

Search Insert Position — predict before coding

Search for a boundary, not a lucky equal element. The desired index is the first position whose value is at least target, which also handles missing targets and duplicates consistently.

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

Presenter notes

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.

Correctness argument: Use the half-open search interval [lo,hi). Every index before lo has value less than target, and every index at or after hi has value at least target. Initially both claims hold vacuously. If nums[mid]<target, sortedness proves all positions through mid are too small, so lo=mid+1 preserves the partition. Otherwise mid and all later positions qualify, so hi=mid preserves it. Each update strictly shrinks the interval. At lo=hi the partition has one boundary, which is the first qualifying index or len(nums) when none qualifies.

Debugging prompt: Test target below all values, above all values, and repeated equal values. Keep hi exclusive; mixing an inclusive-loop condition with this update scheme can index len(nums).

2 / 12

Search a 2D Matrix — predict before coding

Row-major order is globally sorted only because the next row starts above the previous row’s last element. This stronger promise permits one binary search over virtual flattened indices.

Decision: 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?

Presenter notes

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.

Correctness argument: For m rows and n columns, flattened index k maps bijectively to (k/n,k%n). The within-row ordering and cross-row boundary condition make the virtual length-mn array sorted. Ordinary binary-search comparisons therefore discard only positions that cannot hold target. Mapping a midpoint does not allocate a flattened copy, and the search interval shrinks until an equal value is found or no positions remain. A matrix whose rows and columns are individually sorted but whose row ranges overlap does not satisfy this proof and needs a different search strategy.

Debugging prompt: Use column count in both quotient and remainder. Test one row and one column. Do not silently replace the specified row-major ordering with a different matrix-search problem.

3 / 12

Find Peak Element — predict before coding

The array itself need not be monotone. Comparing a midpoint to its right neighbor gives a direction guaranteed to contain some peak, not necessarily the global maximum.

Decision: 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?

Presenter notes

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.

Correctness argument: Treat positions outside the array as negative infinity. Maintain an interval that contains a peak, with boundary slopes pointing inward when needed. If nums[mid]<nums[mid+1], following the ascent to the right must eventually stop at a descent or the right boundary, yielding a peak there; discard through mid. Otherwise adjacent inequality makes nums[mid]>nums[mid+1], and an analogous argument finds a peak in the left portion including mid. Setting hi=mid retains that possible peak. The interval shrinks to one index whose neighbors are lower under the maintained boundary conditions.

Debugging prompt: Validate the returned index against its existing neighbors, not one preferred answer. The loop lo<hi ensures mid+1 is inside the interval. Equal adjacent values are excluded by the contract.

4 / 12

Search in Rotated Sorted Array — predict before coding

Rotation leaves at least one half around the midpoint sorted when values are distinct. Determine which half is ordered before deciding whether the target belongs inside its value range.

Decision: 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.

Presenter notes

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.

Correctness argument: The inclusive interval contains the target if it exists. After checking midpoint equality, compare nums[lo] with nums[mid]. If the left half is sorted, its closed-open value range [nums[lo],nums[mid]) contains target exactly when the remaining left half could contain it; otherwise discard that half. If the left half crosses the rotation point, the right half is sorted, and the analogous range (nums[mid],nums[hi]] decides whether to keep it. Distinct values make this classification unambiguous. Every update excludes the checked midpoint and strictly reduces the interval without discarding a possible target.

Debugging prompt: Test every pivot, an unrotated input, absent targets between values, and both endpoints. The use of <= when recognizing the sorted left half matters for a one-element half.

5 / 12

Find First and Last Position of Element in Sorted Array — predict before coding

An equality range is the difference between two boundaries: first value >=target and first value >target. Two logarithmic searches avoid a linear scan through a long duplicate run.

Decision: 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?

Presenter notes

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.

Correctness argument: The lower-bound search partitions indices into values below target and values at least target. If its result is outside the array or unequal to target, no matching entry exists. Otherwise the upper-bound search partitions values at most target from those strictly greater. Sortedness means all target occurrences form one contiguous block beginning at lower and ending immediately before upper. Returning [lower,upper-1] is therefore exact. The two predicates differ only in strictness, but that difference is what separates the beginning and end of duplicates.

Debugging prompt: Test all-equal arrays, no match, and an empty input. Do not compute upper bound by searching target+1; adding one can overflow at the largest int. The reference compares <=target directly.

6 / 12

Find Minimum in Rotated Sorted Array — predict before coding

The right endpoint identifies which side of the rotation contains the minimum. A midpoint greater than that endpoint lies in the high segment before the minimum.

Decision: 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?

Presenter notes

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.

Correctness argument: The minimum is inside [lo,hi]. If nums[mid]>nums[hi], the pivot and minimum must lie strictly after mid, so lo=mid+1 is safe. Otherwise the subarray from mid through hi is in the low sorted segment or the whole interval is unrotated; mid may itself be the minimum, so retaining it with hi=mid is necessary. Distinctness prevents equality ambiguity except when mid=hi, which the loop excludes. Each step decreases the interval length, and the final index is the unique minimum position.

Debugging prompt: Test a minimum at every position and the length-one case. Do not borrow duplicate-tolerant rules without changing the stated complexity and proof.

7 / 12

Median of Two Sorted Arrays — predict before coding

Take i values from smaller A and j=ceil((m+n)/2)-i from B.

Search cuts 0 through m, including both empty-side boundaries.

Decision: 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.

8 / 12

Median: prove both cut directions

Violation, when both entries exist	Cut update
A[i-1] > B[j]	hi=i-1: fewer A values on the left
B[j-1] > A[i]	lo=i+1: more A values on the left

Decision: A=[5,6], B=[1,2,3,4], i=1, j=2. Why can every larger i also be discarded?

9 / 12

Median: read only existing boundaries

At i=m, A has no right boundary. At i=0, A has no left boundary.

Odd total: maximum existing left value.

Even total: mean of maximum left and minimum right.

Decision: With A=[] and B=[2,6], which values supply the median? Is a fabricated infinity needed?

10 / 12

Change the requested boundary

For [-6,-2,-2,3,8], return the last index with value at most -2.

Derive the equality update. Also handle thresholds -7 and 8 without threshold+1.

11 / 12

Reconstruct and transfer

Write what is already known outside the interval, what remains inside, and why each update shrinks.

Test endpoint arithmetic and absent partition boundaries.

12 / 12