AlgoScope

Ternary Search

Split into thirds with two probes. Useful for unimodal functions, not faster than binary search on arrays.

Searching, algorithm, intermediate
38 sits between 12 and 72, so it can only be in the middle third: low becomes 4 and high becomes 7.active 0-1120518212316423538656772891997109911lowm1m2high72 > 38

Search Variants: Ternary search: two probes, a third kept

Decision, step 3 of 6

38 sits between 12 and 72, so it can only be in the middle third: low becomes 4 and high becomes 7.

How search variants works

Cost

Best
O(1)
Average
O(log n)
Worst
O(log n)
Space
O(1)

More comparisons per step than binary search.

Taught by the same lesson

Search Variants covers these too, in the same run.