PATTERN 7: Binary Search (Index + Answer)
D
Qubits of DPK
April 11, 2026
Core DSA
Core Idea (lock this)
“Search on a monotonic space — not just an array.”
Binary search is not about mid = (l+r)/2.
It’s about YES/NO monotonicity.
How to Recognize This Pattern (CRITICAL)
Think Binary Search when:
- Input is sorted
- Or answer space is monotonic
- You see phrases like:
- Brute force checks all answers linearly
If answer changes from to only once → binary search applies.
30 MUST-DO INTERVIEW PROBLEMS
(10 Easy → 10 Medium → 10 Hard)
EASY (1–10): Index-Based Binary Search
Goal: remove fear of boundaries.
- #Binary Search – LC 704
- #Search Insert Position – LC 35
- #Find First and Last Position of Element in Sorted Array – LC 34
- #Valid Perfect Square – LC 367
- #Sqrt(x) – LC 69
- #Find Peak Element – LC 162
- #Search in Rotated Sorted Array – LC 33
- #Find Minimum in Rotated Sorted Array – LC 153
- #Search a 2D Matrix – LC 74
- #Guess Number Higher or Lower – LC 374
After these:
You should control low, high, and mid confidently.
️ MEDIUM (11–20): Binary Search on Answer
English explanation before code.
- #Koko Eating Bananas – LC 875
- #Capacity to Ship Packages Within D Days – LC 1011
- #Minimum Number of Days to Make Bouquets – LC 1482
- #Find the Smallest Divisor Given a Threshold – LC 1283
- #Split Array Largest Sum – LC 410
- #Magnetic Force Between Two Balls – LC 1552
- #Kth Smallest Element in a Sorted Matrix – LC 378
- #Kth Smallest Pair Distance – LC 719
- #Maximum Value at a Given Index in a Bounded Array – LC 1802
- #Minimum Speed to Arrive on Time – LC 1870
Interview focus:
Can you define the
HARD (21–30): Constraint-Driven Mastery
These separate coders from thinkers.
- #Median of Two Sorted Arrays – LC 4
- #Find Minimum in Rotated Sorted Array II – LC 154
- #Find K-th Smallest Sum of a Matrix With Sorted Rows – LC 1439
- #Minimize Max Distance to Gas Station – LC 774
- #Smallest Rectangle Enclosing Black Pixels – LC 302
- #Maximum Average Subarray II – LC 644
- #Divide Chocolate – LC 1231
- #Kth Smallest Number in Multiplication Table – LC 668
- #Maximum Number of Removable Characters – LC 1898
- #Find in Mountain Array – LC 1095
These test:
- Correct monotonic reasoning
- Boundary precision
- Calm under abstract answer spaces
ONE INTERVIEW LINE YOU SHOULD PRACTICE
Say this naturally:
“The answer space is monotonic, so I can binary search on it.”
That sentence alone signals experience.
Common Interview Killers
- Using binary search without monotonic proof
- Infinite loops (low <= high confusion)
- Wrong mid calculation
- Not testing boundaries
INTERVIEW REVISION CARD — Pattern 7
1️⃣ Pattern in One Line
"Search on a monotonic space — not just sorted arrays, but any YES/NO answer space."
2️⃣ Recognize It When...
- Input is sorted OR answer space is monotonic
- Trigger words: "minimum possible", "maximum possible", "at least/at most", "feasible"
- Brute force checks all answers linearly
- Answer flips from to exactly once
3️⃣ Don't Confuse With...
- Two Pointers (P4) → TP moves both ends; BS narrows mid
- Greedy (P9) → greedy makes sequential choices; BS searches answer space
- Sorting (P6) → sorting prepares input; BS searches it
4️⃣ Approach in 3 Steps
- #Define search space: [low, high]
- #Write check(mid) — is mid feasible/valid?
- #Narrow space: if check passes → try better; else → eliminate half
5️⃣ Invariant to Maintain
"At every step, the answer always lies within [low, high]."
6️⃣ Complexity to Justify
- Time: O(N log N) or O(log N × check cost)
- Space: O(1)
- Why: Each iteration eliminates half the search space
7️⃣ Edge Cases to Always Check
- low = high (single element)
- Answer at boundary (low or high)
- Integer overflow: use low + (high - low) / 2
- Infinite loop: ensure low/high always moves
- off-by-one in low <= high vs low < high
8️⃣ One Line to Say in Interview
"The answer space is monotonic, so I can binary search on it — define check(mid) and halve the space each iteration."