When applying binary search to a sorted array of n items, you look at the -th item to decide whether to continue the search in the first half or in the second half of the array. Consider a ternary search in which you look at the -th and (possibly) the -th items to decide whether to continue the search in the first third, second third, or third third of the array. a) Write a clear and complete algorithm for ternary search of an array. You can write either a recursive or a non-recursive version. b) How many comparisons are done, on average, when using ternary search on an array of size n? Explain. (Try to find an actual formula, not just a "Big- Theta" analysis.) c) Do you think that ternary search is an improvement on binary search? Why or why not