Phase 5Days 22-27

Binary Search — on arrays & on the answer

Halving the search space, and the far more powerful binary-search-on-the-answer

Phase Goal

Master exact search and, crucially, recognizing the monotonic predicate that unlocks answer-search.

Progress

Day 22: Binary search on a sorted array

Sorted order lets you halve the search space each stepThe loop with lo, hi, mid and its exit conditionWhy mid = lo + (hi - lo) / 2 avoids overflowO(log n) and the invariant: the answer stays inside [lo, hi]

Inclusive [lo, hi] versus half-open [lo, hi) templatesThe classic infinite-loop bug and how to prevent itFinding an exact target and returning its indexHand trace on an 8-element array

lower_bound: first index with a[i] >= xupper_bound: first index with a[i] > xFloor and ceil of x in a sorted arrayFirst and last occurrence, and counting occurrences

Choose one core problem from LeetCode, Codeforces, AtCoder, or CSES after checking its prerequisites; hide its technique labelSpend 10–20 minutes retrieving one earlier mechanism and one earlier bug before new work; prioritize weak prerequisitesUse a five-task bank: guided warm-up, core, changed constraint, delayed recall, optional stretch; attempt one or two, not all five on a timerBefore a solution, produce a trace or brute-force plan; when stuck take one hint, act on it, then reassessRecord help used, the failing input, the corrected reasoning, and a next review date; start around 1/3/7/14/30 days and adaptReserve a weekly mixed review; after foundation readiness add a short virtual contest and upsolve one task with known prerequisitesProve progress through a delayed blank-editor reconstruction and a changed problem; a same-day quiz is supporting evidence only

Day 23: Binary search on tricky arrays

Search in a rotated sorted array (no duplicates)Identifying which half is sorted at each stepHandling duplicates (the ambiguous mid case)Finding the minimum and the rotation count

Find a peak element using the slope directionSingle element in a sorted-doubled array via index parityWhy binary search works without full sortedness hereNaming the monotonic property you are exploiting

Reframe search as: find the boundary where a yes/no answer flipsWriting the predicate check(mid) cleanlyThe first-true and last-true templatesThis reframing is the bridge to binary search on the answer

Day 24: Binary search on the answer — part 1

When the answer is a number in a range and feasibility is monotonicGuess the answer, write check(guess), shrink the rangeMinimize-the-maximum and maximize-the-minimum shapesDeriving the search bounds from the constraints

Koko eating bananas (minimum speed)Minimum days to make m bouquetsSmallest divisor given a thresholdCapacity to ship packages within D days

Making the feasibility test O(n) so the total is O(n log range)Integer sqrt and nth root by binary searchOff-by-one in the final answer (return lo versus hi)Proving monotonicity before trusting the approach

Day 25: Binary search on the answer — part 2 (allocation)

Aggressive cows (maximize the minimum distance)Book allocation and split array largest sumPainter's partitionRecognizing they are the same problem in disguise

A greedy count of groups or painters for a candidate valueWhy the greedy check is both correct and fastSetting lo and hi to the tightest valid boundsKth missing positive number by binary search

Mixing up the minimize versus maximize directionWrong initial bounds that miss the answerInteger overflow in sum-based checks (use long long)Validating on the sample by hand

Day 26: Binary search on 2D matrices

Row-sorted, first-of-row-sorted: treat as 1D with index mathSearch in a fully sorted matrix (staircase from a corner)Row with the maximum number of 1sComplexity comparison of each approach

Find a peak element in a 2D gridBinary search on columns with a max-in-column checkWhy the peak always exists in the chosen halfHandling ties and borders

Binary search on the value range, counting elements <= midCounting per row with upper_boundTotal O(n log n log range)Connecting back to answer-search

Day 27: The two-sorted-arrays finale

Merge-count approach O(m+n) as a baselinePartition approach in O(log(min(m,n)))Setting the partition and the four boundary valuesCorrectness of the left-max <= right-min condition

Reduce the median to a kth-element / partition problemHandling even and odd total lengthEdge partitions (empty left/right) with infinity sentinelsWhy this is the hardest common binary-search interview problem

A checklist: sorted? monotonic predicate? bounds?Choosing array search versus answer searchThe reusable first-true templateDebugging: print lo/hi/mid to watch the shrink

Phase Complete!

After this phase, you'll be able to:

Binary search on a sorted array
Binary search on tricky arrays
Binary search on the answer — part 1
Binary search on the answer — part 2 (allocation)
Binary search on 2D matrices
The two-sorted-arrays finale

After Phase 5, explain a core invariant, reconstruct a solution after a delay, diagnose a bug, and solve one unlabelled variation. Repair a failed prerequisite before advancing; record help separately from independent work.

Back to all phases

Binary Search — on arrays & on the answer

Phase Goal

Day 22: Binary search on a sorted array

The core idea

Correct boundaries

lower_bound / upper_bound by hand

Practice, delayed recall, and independent transfer

Day 23: Binary search on tricky arrays

Rotated sorted arrays

Peak and single element

The monotonic-predicate mindset

Practice, delayed recall, and independent transfer

Day 24: Binary search on the answer — part 1

The pattern

Classic problems

Getting check() right

Practice, delayed recall, and independent transfer

Day 25: Binary search on the answer — part 2 (allocation)

The split / allocation family

The greedy feasibility check

Common pitfalls

Practice, delayed recall, and independent transfer

Day 26: Binary search on 2D matrices

Searching a matrix

Peak in 2D & row-wise problems

Median of a row-wise sorted matrix

Practice, delayed recall, and independent transfer

Day 27: The two-sorted-arrays finale

Kth element of two sorted arrays

Median of two sorted arrays

Review & template card

Practice, delayed recall, and independent transfer

Phase Complete!