When applying binary search to a sorted array of n items, you look at the -th it

Question

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?

Explanation / Answer

Solution:

a)

// 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;
}

b)

How many comparisons are done, when there ia an array of size n. (Explain and give an formula).

From the first look, it seems the ternary search does less number of comparisons as it makes Log3n (base 3)recursive calls, but binary search makes Log2n (base 2)recursive calls. Let us take a closer look.
The following is recursive formula for counting comparisons in worst case of Binary Search.

T(n) = T(n/2) + 2, T(1) = 1
The following is recursive formula for counting comparisons in worst case of Ternary Search.

T(n) = T(n/3) + 4, T(1) = 1
In binary search, there are 2Log2n + 1 comparisons in worst case. In ternary search, there are 4Log3n (base 3) + 1 comparisons in worst case.

c)

Is ternary search an improvement on binary search, why or why not.
No.because there are more comparisons in ternarySearch

I hope this helps if you find any problem. Please comment below. Don't forget to give a thumbs up if you liked it. :)

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.