Question

Problem five:

Design an algorithm called which searches for a target t in the sorted subarray , returning the appropriate index if t is found, and 0 if t is not found. TenarySearch will work by dividing the input array into three subarrays of approximately equal length, and calling itself recursively on each subarray.

a. Write pseudo-code for TernarySearch.

b. Write down the recurrence for the run time of TernarySearch and find a tight asymptotic bound on its solution.

Answer 1

`Hey,

Note: If you have any queries related to the answer please do comment. I would be very happy to resolve all your queries.

1)

Begin
   if start <= end then
      midFirst := start + (end - start) /3
      midSecond := midFirst + (end - start) / 3
      if array[midFirst] = key then
         return midFirst
      if array[midSecond] = key then
         return midSecond
      if key < array[midFirst] then
         call ternarySearch(array, start, midFirst-1, key)
      if key > array[midSecond] then
         call ternarySearch(array, midFirst+1, end, key)
      else
         call ternarySearch(array, midFirst+1, midSecond-1, key)
   else
      return invalid location
End

2)

T(n)=T(n/3)+1

So, T(n)=theta(log(n))

Kindly revert for any queries

Thanks.