Binary Search, Partitioning, And Convex Search

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`; runs O(log min(m,n)).

• Sentinel boundaries — use -inf and +inf for empty partition sides; avoids special-casing first/last cuts.

• Odd/even median handling — if total length odd, return max(leftA,leftB); if even, average with min(rightA,rightB).

• Monotonic predicate search — when partition is too far left/right, move lo or hi based on violated inequality.

• Convex/unimodal search — compare f(mid1) and f(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.