
Ternary Search
Introduction
Ternary Search, Ternary Search is a divide-and-conquer algorithm used to find the maximum or minimum of a unimodal function or to search for a specific element in a sorted array.
Unlike binary search, which divides the array into two parts, ternary search splits the range into three equal parts and eliminates one-third in each step.
This approach reduces the search space faster for specific types of problems โ especially when dealing with continuous domains or functions with a clear peak or valley.
Whether you're preparing for coding interviews or trying to optimize a function, understanding ternary search will give you another powerful tool in your algorithm toolbox.
List of Content
- When and Where to Use Ternary Search
- Steps of the Algorithm
- Example: Ternary Search on Sorted Array
- Example: Ternary Search on a Unimodal Function
- Implementation in C++, C and Java
- Time and Space Complexity
- Advantages and Disadvantages
- Conclusion
๐ When and Where to Use Ternary Search
โ Use Ternary Search When:
-
You are dealing with a unimodal function
A unimodal function is one that strictly increases, reaches a single peak or valley, and then strictly decreases (or vice versa).
๐โฌ๏ธโฐ๏ธโฌ๏ธ๐ -
Especially in competitive programming, when you're trying to maximize or minimize a result over a continuous range (like finding the minimum cost or best angle), ternary search is very useful.
-
You have a sorted array and want to find a specific value
It can also be used as an alternative to binary search in a sorted array, though binary search is usually faster in practice.
โ Avoid Ternary Search When:
- The array is not sorted or the function is not unimodal
- Youโre working with discrete data and need exact matches โ binary search is more straightforward and efficient.
๐ Algorithm Steps (for unimodal function or sorted array):
- Calculate two midpoints:
mid1 = low + (high - low) / 3
mid2 = high - (high - low) / 3
- Compare values at mid1 and mid2:
-
If you're looking for a minimum:
- If
f(mid1) < f(mid2)
, discard the right part โhigh = mid2 - 1
- Else, discard the left part โ
low = mid1 + 1
- If
-
If you're looking for a maximum:
- If
f(mid1) > f(mid2)
, discard the right part โhigh = mid2 - 1
- Else, discard the left part โ
low = mid1 + 1
- If
-
Repeat the process until
low
becomes greater thanhigh
or the search range is small enough (e.g., 1 or 2 elements). -
Return the value at the position giving the desired result (min or max).
โ๏ธ Example Loop (in pseudocode):
while (low <= high):
mid1 = low + (high - low) / 3
mid2 = high - (high - low) / 3
if f(mid1) < f(mid2):
high = mid2 - 1
else:
low = mid1 + 1
๐ Example: Ternary Search on a Sorted Array:
Letโs say we want to search for a number in a sorted array using ternary search. The logic is similar to binary search but we split the range into three parts instead of two.
๐ง Example Input:
arr = [2, 4, 10, 15, 20, 25, 30]
target = 15
๐ง Steps:
-
Set
low = 0
,high = 6
(last index) -
Calculate two midpoints:
mid1 = low + (high - low)/3 // 0 + (6 - 0) / 3 = 2
mid2 = high - (high - low)/3 // 6 - (6 - 0) / 3 = 4
So, mid1 = 2 โ arr[2] = 10
, and mid2 = 4 โ arr[4] = 20
- Compare:
- Target
15
is greater than arr[mid1] (10) - But less than arr[mid2] (20)
โ So, search in the middle part:low = mid1 + 1 = 3
,high = mid2 - 1 = 3
- Now only one element left:
- Check
arr[3] = 15
, which is the target ๐ฏ
๐ Example: Ternary Search on a Unimodal Function:
Ternary search is especially useful when you want to find the maximum or minimum value of a unimodal function โ a function that increases up to a point and then decreases (or vice versa).
๐ง Example Problem:
Find the maximum value of the function:
f(x) = -(x - 3)ยฒ + 9
This is a parabola opening downwards, with a maximum at x = 3. We'll use ternary search to find this max value in a continuous domain, say x โ [0, 6].
๐ง Steps:
-
Set
low = 0.0
,high = 6.0
(Weโll work with floating-point values) -
Set a precision value, e.g.,
epsilon = 1e-6
-
While
high - low > epsilon
:
- Calculate midpoints:
mid1 = low + (high - low) / 3
mid2 = high - (high - low) / 3
- Evaluate:
f(mid1) = -(mid1 - 3)^2 + 9
f(mid2) = -(mid2 - 3)^2 + 9
- If
f(mid1) < f(mid2)
, discard left part โlow = mid1
- Else, discard right part โ
high = mid2
- After the loop, return
f(low)
orf(high)
โ both will be very close to the actual maximum.
๐งฎ Result:
The function peaks at x = 3
, and
f(3) = -(3 - 3)^2 + 9 = 9 โ
๐ป Implementation of Ternary Search
Below are simple examples of ternary search to find the maximum of a unimodal function:
f(x) = -(x - 3)ยฒ + 9
in the range [0, 6]
with floating-point precision.
๐ต C++ Implementation
#include <iostream>
#include <cmath>
using namespace std;
double f(double x) {
return -(x - 3) * (x - 3) + 9;
}
double ternarySearch(double low, double high, double eps = 1e-6) {
while (high - low > eps) {
double mid1 = low + (high - low) / 3;
double mid2 = high - (high - low) / 3;
if (f(mid1) < f(mid2))
low = mid1;
else
high = mid2;
}
return f((low + high) / 2);
}
int main() {
double result = ternarySearch(0, 6);
cout << "Maximum value: " << result << endl;
return 0;
}
๐ก Java Implementation
public class TernarySearch {
public static double f(double x) {
return -Math.pow(x - 3, 2) + 9;
}
public static double ternarySearch(double low, double high, double eps) {
while (high - low > eps) {
double mid1 = low + (high - low) / 3;
double mid2 = high - (high - low) / 3;
if (f(mid1) < f(mid2))
low = mid1;
else
high = mid2;
}
return f((low + high) / 2);
}
public static void main(String[] args) {
double max = ternarySearch(0, 6, 1e-6);
System.out.println("Maximum value: " + max);
}
}
๐ด C Implementation
#include <stdio.h>
#include <math.h>
double f(double x) {
return -(x - 3) * (x - 3) + 9;
}
double ternarySearch(double low, double high, double eps) {
while (high - low > eps) {
double mid1 = low + (high - low) / 3;
double mid2 = high - (high - low) / 3;
if (f(mid1) < f(mid2))
low = mid1;
else
high = mid2;
}
return f((low + high) / 2);
}
int main() {
double result = ternarySearch(0.0, 6.0, 1e-6);
printf("Maximum value: %lf\n", result);
return 0;
}
โฑ๏ธ Time and Space Complexity of Ternary Search
Type | Time Complexity | Space Complexity |
---|---|---|
Array-based Ternary Search | O(log n) |
O(1) |
Continuous/Float-based Search | O(log((high-low)/ฮต)) |
O(1) |
๐ Advantages and Disadvantages of Ternary Search
โ Advantages | โ Disadvantages |
---|---|
โก Efficient for unimodal functions | ๐งฎ Slower than binary search (2 comparisons per step) |
๐ Great for optimization problems | ๐ซ Only works for unimodal data/functions |
๐ข Works on arrays & continuous domains | ๐งฉ Slightly harder to implement than binary search |
๐ง Deterministic and easy to analyze | โ๏ธ Limited use in general-purpose searching |
โ Conclusion
Ternary Search is a powerful algorithm in the realm of optimization and unimodal search problems.
By dividing the search space into three parts instead of two, it offers a neat solution to scenarios where you need to find the maximum or minimum value of a function or locate an element in a sorted, unimodal array.
Although it's not a universal replacement for binary search, ternary search is extremely efficient in problems involving mathematical optimization, continuous search spaces, or specific coding contests.
๐ In short:
Use ternary search when you're optimizing within a unimodal domain โ itโs fast, reliable, and elegant for the right type of problems.
Happy Learning! ๐
๐ For more blogs and topics, Click Here.
4 Reactions
0 Bookmarks