Ternary Search

While binary search provides an efficient mechanism to search in a sorted input, there is always an urge to do better on the time complexity.

As we know that binary search works by dividing the input into two partitions and thus yielding in \(O(log_2n)\) complexity, what if we divide the input into three partitions? Can we do better?

Ternary Search, as the name suggests, is based on the same idea. However, it takes the binary search algorithm one step ahead (not necessarily an improvement) and works by dividing the input into three halves. It then identifies the potential search space by comparing the key to the individual partition’s boundaries and thus rejecting 2 out of 3 sections that are not relevant.

On a high level, we would expect the algorithm to result in \(O(log_3n)\) complexity as in every iteration, only 1 of the partition is considered while the other two are rejected but before we conclude it as an improvement, let’s first take a look at the following sample code:

public int ternarySearch(int input[], int key) {
    int start = 0;
    int end = input.length - 1;

    while (end >= start) {
        int midOne = start + (end - start) / 3;
        int midTwo = end - (end - start) / 3;

        // if either of the calculated index
        // contains the key, return the same
        if (input[midOne] == key) {
            return midOne;
        } else if (input[midTwo] == key) {
            return midTwo;
        }

        if (key < input[midOne]) {
            end = midOne - 1;
        } 
        else if (key > input[midTwo]) {
            start = midTwo + 1;
        } else {
            start = midOne + 1;
            end = midTwo - 1;
        }
    }

    return -1;
}

As you can see, we calculate the two middle indices, and then based on the comparison between key and respective index values, we choose 1 of the three partitions and discard the other two.

This gives us an overall time complexity of \(O(log_3n)\), which in theory seem better than the binary search complexity.

But a close look at the implementation mentioned above reveals that for every partition selection, we need to perform 4 comparisons (double than the binary search algorithm).

$$ BS(n) = 2c*log_2(n) $$ $$ TS(n) = 4c* log_3(n) $$

As observed from the respective complexity, the constant factors play a vital role in the total execution time calculation. For practical purposes, even though we are reducing the search space size in every iteration by an additional factor, we are performing double the number of comparisons to identify the next potential partition - which may not yield the expected overall benefits.

And that is why we stop with binary search algorithm working with two partitions, and algorithms like ternary search that work with three or maybe more partitions are not that common.