Consider the problem of taking a sorted array A[1,....,n] of distinct integers,

Question

Consider the problem of taking a sorted array A[1,....,n] of distinct integers, and returning i if there is an element of the array where A[i] = i; if no such element exists then -1 should be returned. For instance, if A ={-2,-1,2,4,8}, then the algorithm should return “4".

Part a: Design an O(log n) decrease-and-conquer algorithm. Give both your pseudocode

and a brief explanation of your algorithm.

Part b: State and solve the recurrence which describes your algorithm's running time.

Show all your work.

Explanation / Answer

a)
The algorithm is that you compare the middle element with its index:

Let us call middle element as 'mid'. Let the array go from 'start' to 'end'.

1) if index > mid
   Then we search in the part of the array from mid+1 to end.
2) if index<mid
   Then we search in the part of the array from start to mid-1.
3) if index=mid
   We found the answer.

b)

At each iteration the array becomes half.

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

In masters theorm a = 1, b = 2, c= 0, log(b)a = 0 and c = 0.

So T(n) = O(n^c logn) which is T(n) = O(logn)

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

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