The recursive algorithm below takes as input an array A of distinct integers, indexed between s and f, and an integer k. The algorithm returns the index of the integer k in the array A, or ?1 if the integer k is not contained within A. Complete the missing portion of the algorithm in such a way that you make three recursive calls to subarrays of approximately one third the size of A. • Write and justify a recurrence for the runtime T(n) of the above algorithm. • Use the recursion tree to show that the algorithm runs in time O(n).
The recursive
f, and an integer k. The algorithm returns the index of the integer k in the array A, or ?1 if the integer
k is not contained within A. Complete the missing portion of the algorithm in such a way that you make
three recursive calls to subarrays of approximately one third the size of A.
• Write and justify a recurrence for the runtime T(n) of the above algorithm.
• Use the recursion tree to show that the algorithm runs in time O(n).
FindK(A,s,f,k)
if s < f
if f = s + 1
if k = A[s] return s
if k = A[f] return f
else
q1 = b(2s + f)=3c
q2 = b(q1 + 1 + f)=2c
... to be continued.
else
... to be continued.
![Algorithm find Inden of K 6s, f, k): Of Ifs ) S+ q«(f as o point i = st pont 2 = St ཀཱ ) for 2 points donde A[s...f] into 3 e](https://media.cheggcdn.com/coop/3ca/3caa29e2-416a-443e-a10b-b7c546eaa9ff/1645765335500_algo_1.jpg)
Trending now
This is a popular solution!
Step by step
Solved in 2 steps with 2 images
