Ternary Search

Given a sorted array, find a target using Ternary search (partition into 3 parts). Discuss which has better worst case performance.

The Idea: Implement binary search, but instead of partitioning in two, we partition into three parts, and recurse onto those depending on where our the value of our current index stands. Even though both have logarithmic time complexity, the most times we split the array, the more if statements that will be needed to iterate through. This is where the constant makes ternary_search perform worse than binary search in the worst case. It will have to iterate down to the finally if statement every time. Consider where n is the size of the array, and k is the number splits. If k == n, then we effectively get k branches of every node. There will only every b a single level in this tree, and checking each branch effectively becomes the same as doing linear search.

Complexity: O(log3(n)) time and O(log3(n)) space

int ternary_search(const vector<int> &ar, int target, int low, int high) {
    if (low <= high) {
        int med3 = low + (high - low)/3;
        int med4 = low + 2*(high - low)/3;

        if (ar[med3] == target)
            return med3;
        else if (ar[med4] == target) {
            return med4;
        }
        else if(target < ar[med3]) {
            return ternary_search(ar, target, low, med3 - 1);
        }
        else if(target < ar[med4]) {
            return ternary_search(ar, target, med3 + 1, med4 - 1);
        }
        else if (target > ar[med4]) {
            return ternary_search(ar, target, med4 + 1, high);
        }
    }
    else {
        return -1;
    }
}