Binary Search, Partitioning, And Convex Search
Asked of: Software Engineer
Last updated

What's being tested
This tests binary search over structure, not just over explicit values: using sorted order, monotonic predicates, and partition invariants to cut the search space. You need to reason about correctness, edge cases, and complexity while keeping implementation clean under interview pressure.
Patterns & templates
-
Partition binary search for median — search smaller array; ensure
`leftA`<=`rightB`&&`leftB`<=`rightA`; runsO(log min(m,n)). -
Sentinel boundaries — use
-infand+inffor empty partition sides; avoids special-casing first/last cuts. -
Odd/even median handling — if total length odd, return
max(leftA,leftB); if even, average withmin(rightA,rightB). -
Monotonic predicate search — when partition is too far left/right, move
loorhibased on violated inequality. -
Convex/unimodal search — compare
f(mid1)andf(mid2)or neighboring samples; shrink toward the lower side. -
Ternary search / golden-section search — for unknown convex functions over continuous domains; stop by precision
eps, not exact equality. -
Complexity discipline — median target should be logarithmic; convex query problems should discuss function-call cost and convergence tolerance.
Common pitfalls
Pitfall: Searching the larger array in median problems can produce invalid complementary partitions or unnecessary boundary complexity.
Pitfall: Treating convex search like ordinary binary search without defining the monotonic signal, such as slope sign or adjacent comparisons.
Pitfall: Forgetting numeric edge cases: empty arrays, duplicate values, integer overflow in averaging, and floating-point termination.
Practice these
The practice cards below cover the canonical variants — solve all of them and time yourself.
Featured in interview prep guides
Practice questions
Related concepts
- Binary Search And Feasibility OptimizationCoding & Algorithms
- Binary Search On AnswerCoding & Algorithms
- Array Search, Selection, And Dynamic ProgrammingCoding & Algorithms
- Sliding Window, Binary Search, and Prefix ReasoningCoding & Algorithms
- Arrays, Intervals, Sliding Windows, And Prefix SumsCoding & Algorithms
- Heaps And Selection AlgorithmsCoding & Algorithms