We have the binary search algorithm. Consider the followingvariant of the algori

Question

We have the binary search algorithm. Consider the followingvariant
of the algorithm, which takes as input a sorted array A[0 . . .n1] of integers and an integer
x:
Algorithm BinarySearch(A[0 . . . n 1], x):
l = 0;
r = n 1;
while l<= r
do m = (l + r)/2;
if x <=A[m]
then r = m
else l = m + 1
endif
endwhile;
if x = A[l]
then return l
else return 1
endif
Prove or disprove the following claim: If x occurs in the array A[0. . . n1], then algorithm
BinarySearch returns an index l such that A[l] = x. If x does notoccur in the array,
then algorithm BinarySearch returns 1.

Explanation / Answer

We will prove this by induction 1st step: when n=1, i =0, if at all x exists in A[] then it should be A[0]... if x=A[0] it returns 1 else it returns -1 Therefore binary search algorithm is true for n=1 2nd step: Assume that Binary search algorithm istrue for all np 3rd step: n>p suppose n=2p, then m=p, Therefore if xA[p], then i=m+1 => i=p+1 if r=p, the array that will be considered is from A[0......p-1]which has p elements. From 2nd step we know that Binary search algorithm is true for alln

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---