AlgoViz: Interactive Algorithm Visualization Tool

Ternary Search

Category: Searching | Time: O(log3 n) | Space: O(1)

Input Data

Visualization

Visual representation of the data structure

Enter an algorithm and input to start visualization.

About Ternary Search

A divide and conquer searching technique. It is similar to binary search but divides the array into three parts and determines which part the key lies in.

Code Editor

The code is for reference. Editing it won't affect the visualization.

function ternarySearch(l, r, key, ar) {
    while (r >= l) {
        let mid1 = l + Math.floor((r - l) / 3);
        let mid2 = r - Math.floor((r - l) / 3);

        if (ar[mid1] == key) {
            return mid1;
        }
        if (ar[mid2] == key) {
            return mid2;
        }

        if (key < ar[mid1]) {
            r = mid1 - 1;
        } else if (key > ar[mid2]) {
            l = mid2 + 1;
        } else {
            l = mid1 + 1;
            r = mid2 - 1;
        }
    }
    return -1;
}

Frequently Asked Questions

About Ternary Search

What is Ternary Search?

How does Ternary Search work?

What is its primary use case?

What is the time complexity of Ternary Search?

Why is Ternary Search often slower than Binary Search?

What is the space complexity?

Does the array need to be sorted?

How does it compare to Jump Search?

When should one absolutely use Ternary Search?

How many comparisons are made in the worst case per iteration?

Where can I learn more?