Question

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 dataset below. List first, last, and mid for each pass through the loop or each recursive method call.

[3, 5, 8, 9, 12, 14, 18, 19, 21, 23, 24, 26]

target = 23

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

[3, 5, 8, 9, 12, 14, 18, 19, 21, 23, 24, 26]

target = 16

Answer 1

Please find your answers below and let me know if you have any doubts or if you need anything to change. If you are satisfied with the solution, please rate the answer. Thanks

Array: [3, 5, 8, 9, 12, 14, 18, 19, 21, 23, 24, 26]

Target: 23

Pass	First	Last	Mid
1	0	11	5
2	6	11	8
3	9	11	10
4	9	9	9

(element 23 is found at index 9 after 4 iterations / recursive calls)

Array: [3, 5, 8, 9, 12, 14, 18, 19, 21, 23, 24, 26]

Target: 16

Pass	First	Last	Mid
1	0	11	5
2	6	11	8
3	6	7	6
4	6	5	6

(Element 16 is not found, a total of 4 recursive calls are made)