Consider the following pseudocode for finding an element in a sorted array A1.n
ID: 3875874 • Letter: C
Question
Consider the following pseudocode for finding an element in a sorted array A1.n 1: BINARYSEARCH(A[1..n], x) 2: left = 1 3: while (right 2 left) mid = left + right-left 5: 6: 7 8: 9: 10 return mid else if a Amid left- mid +1 12: return NOTFOUND (a) State precisely the loop invariant for the while loop in lines 4-11 and prove that this loop invariant holds. Your proof should use the structure of the loop invariant proof presented in Chapter 2 of CLRS Conclude that if r is present in the sorted array A, correctly returns the index of r. (b) Prove by induction that the while loop in lines 4-11 l execute 1 log n times in the worst case. (Hint observe what happens to the size of the subarray Alleft..right] after each iterution.) Conclude that the running time of the BINARYSEARCH algorithm is (log n)Explanation / Answer
a)A:
Hypothesize a loop invariant :
Consider an example
1 2 3 4 5 6 7
-5 10 14 33 42 42 42
we are searching for an element 14 in this array.
so x=14
step 1 : left=1
right=7
mid=left+(right-left)/2 = (2left+right-left)/2 = (left+right)/2
mid=(left+high)/2 = (1+7)/2 = 4
A[4]=33 [here x < 33]
right = mid-1=4-1 = 3
step 2 : left=1
right=3
mid=(left+high)/2 = (1+3)/2 = 2
A[2]=10 [here x >10]
left=mid+1 = 2+1=3
step 3 : left=3
right=3
mid=(left+high)/2 = (3+3)/2 = 3
A[3]=14 [here x ==14]
so it returns mid=3
at each iteration of the while left and right are such that A[left]<=x<=A[right]
This is always valid for any x.
This is loop invariant. It is proved.
b)A: Hypothesize loop variant is inductive:
base case : when the algorithm begins left=1 and right=n. so the target is in between left and right.
Inductive hypothesis : suppose at any iteration of the loop,left and right still contains the search element.
Inductive step : A[mid]>x then the x must lie between left and mid. so right=mid-1
A[mid]<x then the x must lie between right and mid. so left=mid+1
In either cases inductive hypothesis holds in the next loop.
for binary search using inductive hypothesis it takes 1+logn times in the worst case scenario
consider, for binary search:
T(n)=T(n/2)+1
T(n/2)= T(n/4)+1+1
Put the value of The(n/2) in above so T(n)=T(n/4)+1+1 . . . . T(n/2^k)+1+1+1.....+1
=T(2^k/2^k)+1+1....+1 up to k
=T(1)+k
As we taken 2^k=n
K = log n
T(n)=1+logn [worst case]
But the constants are ignored so the running time of the binary search is O(logn).
So Time complexity is O(log n)