Login

Sign Up

Ternary Search
Tushar Varshney

Posted on Jul 5, 2025 | Coding

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:

  1. 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).
    ๐Ÿ“ˆโฌ†๏ธโ›ฐ๏ธโฌ‡๏ธ๐Ÿ“‰

  2. 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.

  3. 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):

  1. Calculate two midpoints:
mid1 = low + (high - low) / 3
mid2 = high - (high - low) / 3

  1. 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 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
  1. Repeat the process until low becomes greater than high or the search range is small enough (e.g., 1 or 2 elements).

  2. 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:

  1. Set low = 0, high = 6 (last index)

  2. 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

  1. 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
  1. 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:

  1. Set low = 0.0, high = 6.0
    (Weโ€™ll work with floating-point values)

  2. Set a precision value, e.g., epsilon = 1e-6

  3. 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
  1. After the loop, return f(low) or f(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

Read next

Tushar Varshney

Tushar Varshney

Jan 6, 25

5 min read

|

Problem on Bubble Sort

Tushar Varshney

Tushar Varshney

Jan 8, 25

6 min read

|

Problem on Selection sort