3. (30 points) Consider an ordered (sorted) array A of size n and the following

Question

3. (30 points) Consider an ordered (sorted) array A of size n and the following ternary search algorithm for finding the index such that Ali-K. Divide the array into three parts. If A[n/3]> K, the first third of the array is searched recursively, else if A[2n/3]> K then the middle part of the array is searched recursively, else the last third of the array is searched recursively. Provisions are also made in the algorithm to return n/3 if n/3] = K, or return 2n/3 if A[2n/3]-K (a) Write the recurrence relation for the number of comparisons C(n) in the average case for the binary and ternary searches and solve the ternary average case only. (b) Do the following experiment (need to write a program in the language of your choice): () Generate arrays of sizes n -500, 1000, 2000, 4000 and 8000. Fill the arrays as follows: AlU- integer(8xvi) 012,..,. -1.

Explanation / Answer

Please find my analysis between Binary Search and Ternary Search.

########## Binary Search #########

int binarySearch(int arr[], int l, int r, int x)
{
if (r >= l)
{
int mid = l + (r - l)/2;
  
// If the element is present at the middle itself
if (arr[mid] == x) return mid;
  
// If element is smaller than mid, then it can only be present
// in left subarray
if (arr[mid] > x) return binarySearch(arr, l, mid-1, x);
  
// Else the element can only be present in right subarray
return binarySearch(arr, mid+1, r, x);
}
  
// We reach here when element is not present in array
return -1;
}

########## Ternary Search #########

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

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 + 1 comparisons in worst case.

Related Questions

Navigate

• Browse (All)
• Browse 3
• Subjects

---

---

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