Question

1. [3] Is the following version of binary search algorithm correct? Algorithm 1 Version of Binary search function BSEARCH(A, first, last, key) if first > last then return -1; end if mid= [(first + last)/2]; if key == A[mid) then return mid; end if if key <Amid then return BSEARCH(A, first, mid, key) else return BSEARCH(A, mid+ 1, last, key) end if end function 1. no, counterexample of input: A = (1,3,6,7, 12, 15, 32, 471, first = 1, last = 8, key = 32 ii. yes III. no, counterexample of input: A = (1,3,6,7,12, 15, 32, 47), first = 1, last = 8, key = 22 iv. no, counterexample of input: A = (5), first = 1, last = 1, key = 3 v. no, counterexample of input: A = (5), first = 1, last = 1, key = 5

Answer 1

The above-given algorithm is not correct. and the counter-example for the same is option 3

A = [1 ,3,6,7,12,15,32,47]
1st Iteration: first =1, last = 8, mid = 4 => a[mid] < key => first = mid+1, last = last
2nd Iteration first = 5, last = 8, mid = 6, => a[mid] < key => first = mid+1, last = last
3rd Iteration first = 7, last = 8, mid = 7 => a[mid] > key =>first = first, last = mid
4th Iteration first = 7, last = 7, mid = 7 => a[mid] > key => first = frist, last = mid
5th Iteration first = 7, last = 7, mid = 7

Thus 4th and 5th iterations are both same thus it will not make any difference, thus we won't be able to reach to our solution.

That was a nice question to answer
Friend, If you have any doubts in understanding do let me know in the comment section. I will be happy to help you further.
Thanks