Ternary Search
Checks two points that split a sorted array into thirds and keeps only the third that can still hold the target.
How it works
Ternary search is like binary search, but it splits the range into three parts instead of two. It keeps a range, low to high, and checks the values at two points, mid1 and mid2, one third and two thirds of the way across:
- If either value equals the target, it returns that index.
- If the target is smaller than the first value, it can only be in the left third.
- If the target is larger than the second value, it can only be in the right third.
- Otherwise it is between them, in the middle third.
Every round shrinks the range to a third. When the range is empty, the target is not in the array and it returns -1.
When to use it
Cutting to a third sounds faster than cutting in half, but each round costs two checks instead of one. In the worst case, ternary search makes about 2·log₃ n ≈ 1.26·log₂ n comparisons, which is more than binary search's log₂ n. For searching a sorted array, binary search wins.
Where ternary search does shine is finding the peak or valley of a unimodal function (one that rises then falls), where comparing the two points tells you which third can't hold the peak. Binary search can't do that with a single point.
Complexity
| Case | Time | When |
|---|---|---|
| Best | O(1) | The target is at one of the first two points |
| Average | O(log n) | Each round keeps a third of the range |
| Worst | O(log n) | The target is found last, or the range runs out |
| Extra space | Why |
|---|---|
| O(1) | It only keeps the low, high, mid1 and mid2 indexes |
Implementations
function ternarySearch(array, target) {
let low = 0;
let high = array.length - 1;
while (low <= high) {
const third = Math.floor((high - low) / 3);
const mid1 = low + third;
const mid2 = high - third;
const value1 = array[mid1];
const value2 = array[mid2];
if (value1 === target) return mid1;
if (value2 === target) return mid2;
if (target < value1) {
high = mid1 - 1;
} else if (target > value2) {
low = mid2 + 1;
} else {
low = mid1 + 1;
high = mid2 - 1;
}
}
return -1;
}
def ternary_search(array, target):
low, high = 0, len(array) - 1
while low <= high:
third = (high - low) // 3
mid1 = low + third
mid2 = high - third
value1, value2 = array[mid1], array[mid2]
if value1 == target:
return mid1
if value2 == target:
return mid2
if target < value1:
high = mid1 - 1
elif target > value2:
low = mid2 + 1
else:
low, high = mid1 + 1, mid2 - 1
return -1
#include <vector>
int ternarySearch(const std::vector<int>& a, int target) {
int low = 0;
int high = static_cast<int>(a.size()) - 1;
while (low <= high) {
int third = (high - low) / 3;
int mid1 = low + third;
int mid2 = high - third;
if (a[mid1] == target) return mid1;
if (a[mid2] == target) return mid2;
if (target < a[mid1]) {
high = mid1 - 1;
} else if (target > a[mid2]) {
low = mid2 + 1;
} else {
low = mid1 + 1;
high = mid2 - 1;
}
}
return -1;
}