Problem 2: The ternary search algorithm is a modification of the binary search a

Question

Problem 2: The ternary search algorithm is a modification of the binary search algorithm that splits the input not into two sets of almost-equal sizes, but into three sets of sizes approximately one-third.
a) Verbally describe and write pseudo-code for the ternary search algorithm.
b) Give the recurrence for the ternary search algorithm
c) Solve the recurrence to determine the asymptotic running time of the algorithm. How does the running time of the ternary search algorithm compare to that of the binary search algorithm.

Explanation / Answer

Ternary search is inspired from the binary search algorithm.Here the array is divided into 3 parts instead of 2 as in binary search.

Initially we take 2 mid values,one is n/3 rd element and other is 2/3rd element.

Based on the comparision with 2 mids,we search on only one part of 3 parts.

Pseudo Code:

Initially r = N-1 and l = 0.

ternarySearch(l,r,x)

if (r >= l)

   {

mid1 := l + (r - l)/3;

mid2 := mid1 + (r - l)/3;

// If x is present at the mid1

        if (arr[mid1] = x) then return mid1;

// If x is present at the mid2

        if (arr[mid2] = x) then return mid2;

// If x is present in left one-third

        if (arr[mid1] > x) then return ternarySearch(l, mid1-1, x);

// If x is present in right one-third

        if (arr[mid2] < x) then return ternarySearch(arr, mid2+1, r, x);

// If x is present in middle one-third

otherwise return ternarySearch(arr, mid1+1, mid2-1, x);

   }

   // We reach here when element is not present in array

   return -1;

Running TIme:

The recurssive relation is :

T(n) = T(n/3) + 4 // 4 is the number of comparisions.

i.e., we divide the n element array into n/3 elements each time.

So By solving using Master theorem we get

T(n) = 4Log3n + 1.

So the Time Complexity is:O(Log3N) where N is the number of elements.

Note:Binary Search is preffered over ternary search.



Thanks, let me know if there is any concern.

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

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