Ternary Search

Splits the sorted window into thirds with two probes per step, discarding two-thirds — or the middle third — each round. It makes more comparisons per step than binary search, so in practice binary search is faster, but it is a clean illustration of multi-way divide-and-conquer.

Best

O(1)

Average

O(log₃ n)

Worst

O(log₃ n)

Space

O(1)