Lori first coded recursive binarySearch() as follows. Where did she go wrong?

Question

```
public static int binarySearch( int[]coll, int target ) {
int first = 0,
last = target.length,
mid = ( first + last ) / 2;
if ( first > last ) return -1; // failure — base case
if ( coll[ mid ] == target ) // success — base case
return mid;
if ( coll[ mid ] < target ) { // recursive cases
last = mid – 1;
return binarySearch( coll, target );
}
else {
first = mid + 1;
return binarySearch( coll, target );
}
}

Answer 1

The mistake is in the recursive part and has to do with first and last, which are reset to '0' and 'target.length' in the beginning of each call. Consequently, the search does not progress toward the base case and will continually check the same midpoint over and over. Each invocation should narrow the search. This can be done by passing in the bounds of the search space as parameters, as is suggested in the chapter.