Question

Given a sorted array of distinct integers a [0 . . . N-1], find out whether there is an index i for which a[i] = k where k is the given key. Give a divide-and-conquer algorithm that runs in time o(log n).

Answer 1

Answer:

By Sahil kumar ( 17BCS2904 ).... see explanation.

Explanation:

Algo(A[1,.......,n-1)

1. if n==1, return (A[n]==n)

2. m=(n/2)

3. if A[m] =m , return (true)

4. else if A[m]>m, return (Algo(A[1,.....,m-1]))

5. else return (Algo(A[m+1,....,n]))

Each division reduce the problem size by half, and we do a constant

amount of work in each function call.  This gives us the following re- currence relation:-

T(n) =T(n/2) +O(1)  

which solves to   T(n) =O(log n).