The following shows the ternary search algorithm for searchi

The following shows the ternary search algorithm for searching in a sorted array S[1..n]. If n = 1, simply compare the search key k with the single element of the array; otherwise, search recursively by comparing k with S[n/3], and if k is larger, compare it with S[2n/3] to determine in which third of the array to continue the search. (2.1) What design technique is this algorithm based on? (2.2) Write a recursive algorithm to perform the operation. (2.3) Set up a recurrence for the number of key comparisons in the worst case. You may assume that n is a positive integer and a power of 3. (2.4) Solve the recurrence for n. (2.5) Compare this algorithm\'s efficiency with that of binary search.

Solution

2.1) This algorithm is based on Recursion.

2.2)

The following is a simple recursive Ternary Search function in C++.

// A recursive ternary search function. It returns location of x in

// given array arr[l..r] is present, otherwise -1

int ternarySearch(int arr[], int l, int r, int x)

{

   if (r >= l)

   {

        int mid1 = l + (r - l)/3;

        int mid2 = mid1 + (r - l)/3;

        // If x is present at the mid1

        if (arr[mid1] == x) return mid1;

        // If x is present at the mid2

        if (arr[mid2] == x) return mid2;

        // If x is present in left one-third

        if (arr[mid1] > x) return ternarySearch(arr, l, mid1-1, x);

        // If x is present in right one-third

        if (arr[mid2] < x) return ternarySearch(arr, mid2+1, r, x);

        // If x is present in middle one-third

        return ternarySearch(arr, mid1+1, mid2-1, x);

   }

   // We reach here when element is not present in array

   return -1;

}

2.3,2.4)

Which of the above two does less comparisons in worst case?
By looking, it seems the ternary search does less number of comparisons as it makes Log₃n recursive calls, but binary search makes Log₂n recursive calls. Let us take a closer look.
The following is recursive formula for counting comparisons in worst case of Binary Search.

The following is recursive formula for counting comparisons in worst case of Ternary Search.

In binary search, there are 2Log₂n + 1 comparisons in worst case. In ternary search, there are 4Log₃n + 1 comparisons in worst case.

As mentioned n is a power of 3. let n = n^x

In ternary search, there are 4x + 1 comparisons in worst case.

Therefore, the comparison of Ternary and Binary Searches boils down the comparison of expressions 2Log₃n and Log₂n . The value of 2Log₃n can be written as (2 / Log₂3) * Log₂n . Since the value of (2 / Log₂3) is more than one, Ternary Search does more comparisons than Binary Search in worst case.