Question

# Problem five: Design an algorithm called which searches for a target t in the sorted subarray...

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.

`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.