Ternary Binary Search. Write pseudocode for a boolean function search, that perf

Question

Ternary Binary Search. Write pseudocode for a boolean function search, that performs a ternary search for an integer x in an integer array A (sorted in increasing order), returning true if x is found in the array and false otherwise. A ternary function generalizes binary search by splitting the input into three sets of sizes approximately one third. The function header must be: bool search( A, x, l, r) where 1 is the left index and r is the right index into the array. The function is invoked as search( A, x, 0, n-1 ) for an array of size n. Write a recurrence for the worst case run time of the function search in part (a) as a function of n. and obtain its order using the Master Theorem.

Explanation / Answer

static boolean search (int[] A, int value, int start, int end)
{
if (start > end) {
return false;
}

// First boundary: add 1/3 of length to start.
   int mid1 = start + (end-start) / 3;
  
// Second boundary: add 2/3 of length to start.
   int mid2 = start + 2*(end-start) / 3;

   if (A[mid1] == value) {
   return true;
   }
   else if (A[mid2] == value) {
   return true;
   }
   else if (value < A[mid1]) {
   // Search 1st third.
   return search (A, value, start, mid1-1);
   }
   else if (value > A[mid2]) {
   // Search 3rd third.
   return search (A, value, mid2+1, end);
   }
   else {
   // Middle third.
   return search (A, value, mid1,mid2);
   }
}

Time Complexity:

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

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

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

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