Ternary Search
Ternary search is similar to binary search but divides the array into three parts using two midpoints. It works on sorted arrays and finds the maximum/minimum of a unimodal function. Time complexity O(log₃ n), which is slightly slower than binary search O(log₂ n) for the same input size, but it's used for unimodal functions where the function is increasing then decreasing (or vice versa).
Java implementation for finding maximum in a unimodal array:
public static int ternarySearchMax(int[] arr) {
int left = 0, right = arr.length - 1;
while (left < right) {
int mid1 = left + (right - left) / 3;
int mid2 = right - (right - left) / 3;
if (arr[mid1] < arr[mid2]) {
left = mid1 + 1;
} else if (arr[mid1] > arr[mid2]) {
right = mid2 - 1;
} else {
left = mid1 + 1;
right = mid2 - 1;
}
}
return arr[left];
}
Ternary search is rarely used for simple arrays because binary search is simpler and faster. Its main application is for unimodal functions (like finding the peak in a mountain array) where the array is not strictly sorted.
Two Minute Drill
- Ternary search divides range into three parts using two midpoints.
- Time O(log₃ n) but constant factor larger than binary search.
- Useful for unimodal functions (first increasing, then decreasing).
- Less common in practice than binary search.
Need more clarification?
Drop us an email at career@quipoinfotech.com