348. Is splitting a sorted array into three parts (ternary search) faster than binary search? What binary search variants should you know?
MediumDivide & conquer
Show model answer
No, for sorted arrays. Ternary search uses up to two comparisons per level to cut the range to a third, so worst case about 2·log₃ n ≈ 1.26·log₂ n comparisons versus log₂ n for binary search. Both are O(log n) time and O(1) space iteratively, but binary search has the smaller constant. Ternary search is genuinely useful for finding the peak of a unimodal function over a continuous domain.
Useful binary search variants: first occurrence (lower bound), last occurrence (upper bound minus one), first element ≥ x, searching a rotated array, and binary search on the answer (for example the smallest capacity that ships packages in D days). Compute the midpoint as `lo + (hi - lo) / 2` in languages with fixed-width integers to avoid overflow, and be deliberate about whether the interval is closed or half-open.