(A). Lori first coded recursive binarySearch() as follows. Where did she go wron
ID: 3640790 • Letter: #
Question
(A). Lori first coded recursive binarySearch() as follows. Where did she go wrong?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 );
}
}
(B). We can describe the Merge-Sort algorithm on an array of n elements, where n is a power of 2 (i.e., 2, 4, 8, 16, 32, etc.), informally as follows:
1. If n = 2, return a list of the two elements sorted, lowest first.
2. If n > 2, recursively Merge-Sort the left (low-index) half of the array, to produce a sorted list L1, and recursively sort the right (high-index) half of the array to produce a sorted list L2.
3. Merge L1 and L2 to produce a single sorted list.
Explanation / Answer
In the first one, Lori is calling the same method inside the method you will see:
public static int binarySearch ( int[] coll, int target )
{
int first = 0,
last = target.length, missing ;
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 );
}
}
you cann't return the same mothod inside the method.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.