Part a deals with the recursive version of binary search Po

Part (a) deals with the recursive version of binary search: // Post: Returns 1 iff target is in arrlo..len-1, 0 otherwise. int BinarySearch (int arr, int len, int target) if (len 0) int mid len/2 if (targetarr(mid]) return 1 if (target

Solution

Hi, Please find solution for b). I have no idea about question d) concept.

int BinarySearch(int A[],int len, int target)
{
int first = 0;
int last = len-1;

while( last - first > 1 )
{
int mid = (last+first)/2;

if( A[mid] <= target )
first = mid;
else
last = mid;
}

if( A[first] == target )
return first;
else
return -1;
}

In the while loop we are depending only on one comparison. The search space converges to place l and r point two different consecutive elements. We need one more comparison to trace search status.