Question

Java

The following questions ask about tracing a binary search. To trace the binary search, list the value of first, last, and mid for each pass through the loop or method.

Use one of these methods for your trace.

public static int binarySearchIterative(int[] numbers, int target) {

boolean found = false;

int first = 0;

int last = numbers.length - 1;

while (first <= last && !found) {

int mid = (first + last) / 2;

if (numbers[mid] == target) {

targetLocation = mid;

found = true;

} else if (numbers[mid] < target) {

first = mid + 1;

} else { // numbers[mid] > target

last = mid - 1;

}

}

return targetLocation;

}

public static int binarySearchRecursive(int[] numbers, int target) {

return binarySearchRecursiveHelper(numbers, target, 0, numbers.length - 1);

}

private static int binarySearchRecursiveHelper(int[] numbers, int target, int first, int last) {

int mid = ((last - first) / 2) + first;

if (first > last) {

return -1; // indices cross over

} else if (target == numbers[mid]) {

return mid; // we found it!

} else if (target < numbers[mid]) {

return binarySearchRecursiveHelper(numbers, target, first, mid - 1);

} else { // target > numbers[mid]

return binarySearchRecursiveHelper(numbers, target, mid + 1, last);

}

}

1) Trace binary search on the sorted dataset below. List first, last, and mid for each pass through the loop or each recursive method call.

target = 15

index: 0 1 2 3 4 5 6 7 8 9 10 11

value: 12 15 19 23 25 27 36 39 47 58 62 67

2) Trace binary search on the sorted dataset below. List first, last, and mid for each pass through the loop or each recursive method call.

target = 33

index: 0 1 2 3 4 5 6 7 8 9 10 11

value: 12 15 19 23 25 27 36 39 47 58 62 67

Answer 1