Ternary search
Ternary search splits the remaining range into three roughly equal parts using two markers, compares the target against the value at each marker, and narrows to whichever third the target must be in — the first third, the last third, or the middle third between the two markers.
When it is the right choice
Ternary search is the right tool for one specific job it is not built for here: finding the peak or trough of a unimodal function, where each step needs two evaluations to know which slope you are on — a genuinely different problem from searching a sorted array. For searching a sorted array, which is what this tool shows, it is strictly worse than binary search: it makes two comparisons per step instead of one, while only cutting the range by a factor of three instead of two, and the coarser cut does not make up for the extra comparison. There is no honest case for choosing it over binary search here; it earns its page for showing that plainly.
How it works
- Set the low and high boundaries to the first and last position of the array.
- Place two markers a third and two-thirds of the way across the remaining range.
- Compare the value at the first marker with the target; if it matches, the target is found.
- Compare the value at the second marker with the target; if it matches, the target is found.
- If the target is smaller than the first marker, search the first third of the range. If it is larger than the second marker, search the last third. Otherwise search the middle third, between the two markers.
Worth noticing
- Averaged over every target it makes more comparisons than binary search, not fewer — two per step against binary search's one, while cutting the range by a factor of three rather than two. Three thirds do not pay for the second comparison. A single lucky search can still beat it: if a marker lands on the target immediately, ternary search finishes in one comparison. The average is the honest measure, not one run.
- It is a genuine improvement over binary search only for the different problem of finding an extremum of a unimodal function, where a single comparison cannot tell you which direction to go the way it can in a sorted array.
Cost
- Best
- O(1)
- Average
- O(log n)
- Worst
- O(log n)
- Extra space
- O(1)