← Back to DSA Course | Chapter 10: Searching Algorithms | Lesson 4 of 5

Ternary Search

In this page:

  1. What is Ternary Search
  2. How It Works
  3. Reduce Range
  4. Complexity
  5. Use Cases

What is Ternary Search

Ternary search divides the current search range into three roughly equal parts using two midpoints instead of one, then compares the target against both midpoints to decide which third of the range can be safely discarded.

Example: What is Ternary Search

#include <iostream>
using namespace std;
int main() {
    int arr[] = {1,3,5,7,9,11,13};
    int lo = 0, hi = 6;
    int mid1 = lo + (hi - lo) / 3;
    int mid2 = hi - (hi - lo) / 3;
    cout << "mid1=" << arr[mid1] << " mid2=" << arr[mid2] << endl;
    return 0;
}
public class Main {
    public static void main(String[] args) {
        int[] arr = {1,3,5,7,9,11,13};
        int lo = 0, hi = 6;
        int mid1 = lo + (hi - lo) / 3;
        int mid2 = hi - (hi - lo) / 3;
        System.out.println("mid1=" + arr[mid1] + " mid2=" + arr[mid2]);
    }
}
arr = [1, 3, 5, 7, 9, 11, 13]
lo, hi = 0, 6
mid1 = lo + (hi - lo) // 3
mid2 = hi - (hi - lo) // 3
print("mid1=", arr[mid1], "mid2=", arr[mid2])
#include <stdio.h>
int main() {
    int arr[] = {1,3,5,7,9,11,13};
    int lo = 0, hi = 6;
    int mid1 = lo + (hi - lo) / 3;
    int mid2 = hi - (hi - lo) / 3;
    printf("mid1=%d mid2=%d\n", arr[mid1], arr[mid2]);
    return 0;
}

How It Works

Two values, typically called mid1 and mid2, split the range into three sections; comparing the target against both of them determines which one or two of the three sections cannot contain the target and can be eliminated from further search.

Example: How It Works

#include <iostream>
using namespace std;
int main() {
    int arr[] = {1,3,5,7,9,11,13}, target = 9;
    int lo = 0, hi = 6;
    int mid1 = lo + (hi - lo) / 3, mid2 = hi - (hi - lo) / 3;
    if (arr[mid1] == target) cout << "Found at mid1";
    else if (arr[mid2] == target) cout << "Found at mid2";
    else cout << "Not at either midpoint yet";
    return 0;
}
public class Main {
    public static void main(String[] args) {
        int[] arr = {1,3,5,7,9,11,13};
        int target = 9;
        int lo = 0, hi = 6;
        int mid1 = lo + (hi - lo) / 3, mid2 = hi - (hi - lo) / 3;
        if (arr[mid1] == target) System.out.println("Found at mid1");
        else if (arr[mid2] == target) System.out.println("Found at mid2");
        else System.out.println("Not at either midpoint yet");
    }
}
arr = [1, 3, 5, 7, 9, 11, 13]
target = 9
lo, hi = 0, 6
mid1 = lo + (hi - lo) // 3
mid2 = hi - (hi - lo) // 3
if arr[mid1] == target:
    print("Found at mid1")
elif arr[mid2] == target:
    print("Found at mid2")
else:
    print("Not at either midpoint yet")
#include <stdio.h>
int main() {
    int arr[] = {1,3,5,7,9,11,13}, target = 9;
    int lo = 0, hi = 6;
    int mid1 = lo + (hi - lo) / 3, mid2 = hi - (hi - lo) / 3;
    if (arr[mid1] == target) printf("Found at mid1\n");
    else if (arr[mid2] == target) printf("Found at mid2\n");
    else printf("Not at either midpoint yet\n");
    return 0;
}

Reduce Range

Depending on the comparison results, either the leftmost third, the rightmost third, or both the leftmost and rightmost thirds are discarded, leaving only the middle third (or a two-thirds range in some cases) to continue searching within.

Example: Reduce Range

#include <iostream>
using namespace std;
int main() {
    int arr[] = {1,3,5,7,9,11,13}, target = 11;
    int lo = 0, hi = 6;
    int mid1 = lo + (hi - lo) / 3, mid2 = hi - (hi - lo) / 3;
    if (target < arr[mid1]) hi = mid1 - 1;
    else if (target > arr[mid2]) lo = mid2 + 1;
    else { lo = mid1 + 1; hi = mid2 - 1; }
    cout << "New range: [" << lo << "," << hi << "]" << endl;
    return 0;
}
public class Main {
    public static void main(String[] args) {
        int[] arr = {1,3,5,7,9,11,13};
        int target = 11;
        int lo = 0, hi = 6;
        int mid1 = lo + (hi - lo) / 3, mid2 = hi - (hi - lo) / 3;
        if (target < arr[mid1]) hi = mid1 - 1;
        else if (target > arr[mid2]) lo = mid2 + 1;
        else { lo = mid1 + 1; hi = mid2 - 1; }
        System.out.println("New range: [" + lo + "," + hi + "]");
    }
}
arr = [1, 3, 5, 7, 9, 11, 13]
target = 11
lo, hi = 0, 6
mid1 = lo + (hi - lo) // 3
mid2 = hi - (hi - lo) // 3
if target < arr[mid1]:
    hi = mid1 - 1
elif target > arr[mid2]:
    lo = mid2 + 1
else:
    lo, hi = mid1 + 1, mid2 - 1
print("New range:", [lo, hi])
#include <stdio.h>
int main() {
    int arr[] = {1,3,5,7,9,11,13}, target = 11;
    int lo = 0, hi = 6;
    int mid1 = lo + (hi - lo) / 3, mid2 = hi - (hi - lo) / 3;
    if (target < arr[mid1]) hi = mid1 - 1;
    else if (target > arr[mid2]) lo = mid2 + 1;
    else { lo = mid1 + 1; hi = mid2 - 1; }
    printf("New range: [%d,%d]\n", lo, hi);
    return 0;
}

Complexity

Because each step reduces the range to roughly one third rather than one half, ternary search needs about 1.71 times as many comparisons per elimination step as binary search — despite the appealing three-way idea, it's not actually faster than binary search for simple value lookup.

Example: Complexity

#include <iostream>
using namespace std;
int main() {
    int n = 1000000;
    double ternarySteps = log(n) / log(3) * 2;
    double binarySteps = log(n) / log(2);
    cout << "Ternary needs ~1.71x more comparisons per elimination than binary" << endl;
    return 0;
}
public class Main {
    public static void main(String[] args) {
        int n = 1000000;
        System.out.println("Ternary needs ~1.71x more comparisons per elimination than binary");
    }
}
n = 1_000_000
print("Ternary needs ~1.71x more comparisons per elimination than binary")
#include <stdio.h>
int main() {
    printf("Ternary needs ~1.71x more comparisons per elimination than binary\n");
    return 0;
}

Use Cases

Ternary search's real value is on unimodal functions — functions that strictly increase then strictly decrease (or vice versa) — where it can find the maximum or minimum point efficiently, which is a different kind of problem than searching for a specific stored value.

Example: Use Cases

#include <iostream>
using namespace std;
int f(int x) { return -(x-5)*(x-5) + 20; }
int main() {
    int lo = 0, hi = 10;
    while (hi - lo > 2) {
        int mid1 = lo + (hi - lo) / 3, mid2 = hi - (hi - lo) / 3;
        if (f(mid1) < f(mid2)) lo = mid1 + 1; else hi = mid2 - 1;
    }
    cout << "Peak near x=" << lo << endl;
    return 0;
}
public class Main {
    static int f(int x) { return -(x-5)*(x-5) + 20; }
    public static void main(String[] args) {
        int lo = 0, hi = 10;
        while (hi - lo > 2) {
            int mid1 = lo + (hi - lo) / 3, mid2 = hi - (hi - lo) / 3;
            if (f(mid1) < f(mid2)) lo = mid1 + 1; else hi = mid2 - 1;
        }
        System.out.println("Peak near x=" + lo);
    }
}
def f(x):
    return -(x - 5) ** 2 + 20

lo, hi = 0, 10
while hi - lo > 2:
    mid1 = lo + (hi - lo) // 3
    mid2 = hi - (hi - lo) // 3
    if f(mid1) < f(mid2):
        lo = mid1 + 1
    else:
        hi = mid2 - 1
print("Peak near x=", lo)
#include <stdio.h>
int f(int x) { return -(x-5)*(x-5) + 20; }
int main() {
    int lo = 0, hi = 10;
    while (hi - lo > 2) {
        int mid1 = lo + (hi - lo) / 3, mid2 = hi - (hi - lo) / 3;
        if (f(mid1) < f(mid2)) lo = mid1 + 1; else hi = mid2 - 1;
    }
    printf("Peak near x=%d\n", lo);
    return 0;
}
🔒

Chapter Quiz — Complete all 5 topics to unlock

0/5 topics done

Complete these topics first:

← Previous Lesson Binary Search on Answer Next Lesson → Jump Search

Login to run this code

C/C++/Java/PHP execution requires a free account. Your code is saved — you'll land right back in the editor after logging in.