Ternary Search

Ternary search is binary search with one more probe. Rather than checking a single midpoint, it places two markers at a third and two-thirds of the way across the window, splitting it into three roughly equal pieces. Comparing the target against both probes tells you which piece it must live in — the left third, the middle third, or the right third — and the other two are thrown away in one round. Because each round divides the window by three instead of two, it needs fewer rounds than binary search: about log base three of n rather than log base two.

Fewer rounds sounds like a win, but the accounting is subtler. Each round of ternary search costs up to two equality checks and two order comparisons, where binary search spends just one probe. Multiply it out and ternary search does more total comparisons than binary search to cover the same array, even though it takes fewer iterations to get there. That is the classic lesson here: a smaller number of steps is not the same as less work. It is still firmly O(log n), and it remains a clean illustration of divide-and-conquer, but it is why binary search, not ternary, is the one everyone reaches for.

Watch the shaded band split at its two probe points each round and collapse onto whichever third survives. Type a value into the search box to look for something specific, or leave it empty and let the Target menu pick one that is present or falls in a gap. Data switches between numbers and words, and New array deals a fresh sorted set.