Consider ternary search—the following algorithm for searching in a sorted array A[0..n −...

Consider ternary search—the following algorithm for searching in a sorted array A[0..n − 1]. If n = 1, simply compare the search key K with the single element of the array; otherwise, search recursively by comparing K with and if K is larger, compare it with to determine in which third of the array to continue the search.

a. What design technique is this algorithm based on?

b. Set up a recurrence for the number of key comparisons in the worst case. You may assume that n = 3^k.

c. Solve the recurrence for n = 3^k.

d. Compare this algorithm’s efficiency with that of binary search.