AP Computer Science Exam Question:

Consider the following code snippet:

public class BinarySearch {

  public static int binarySearch(int[] arr, int target) {
    int left = 0;
    int right = arr.length - 1;
    
    while (left <= right) {
      int mid = left + (right - left) / 2;
      
      if (arr[mid] == target) {
        return mid;
      }
      
      if (arr[mid] < target) {
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }
    
    return -1;
  }

  public static void main(String[] args) {
    int[] arr = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
    int target = 23;
    
    int result = binarySearch(arr, target);
    
    System.out.println("Index of target: " + result);
  }

}

Assume the given code implements the binary search algorithm to find the index of a target element in a sorted array.

Write the step-by-step process of how this algorithm works to find the index of the target element. Include an explanation of the variables and their roles in the algorithm.

Answer:

The given code implements the binary search algorithm to find the index of a target element in a sorted array. Here is the step-by-step process of how the algorithm works:

1. The binarySearch method takes two parameters: the sorted array arr and the target element target. It returns the index of the target element if found, or -1 if the target element is not present in the array.

2. Initially, the left pointer is set to 0, pointing to the first element of the array, and the right pointer is set to arr.length - 1, pointing to the last element of the array.

3. The algorithm enters a while loop, which continues as long as the left pointer is less than or equal to the right pointer. This condition ensures that the algorithm searches within the valid range of the array.

4. Inside the while loop, the mid pointer is calculated as left + (right - left) / 2. This finds the middle index between the left and right pointers.

5. The algorithm checks if the element at the middle index (arr[mid]) is equal to the target element. If it is, the index of the target element is returned, and the algorithm terminates.

6. If arr[mid] is less than the target element, it means the target element is likely to be in the right half of the array. In this case, the left pointer is updated to mid + 1 to narrow down the search range.

7. If arr[mid] is greater than the target element, it means the target element is likely to be in the left half of the array. In this case, the right pointer is updated to mid - 1 to narrow down the search range.

8. Steps 4-7 are repeated until the left pointer becomes greater than the right pointer. At this point, the target element is not present in the array, and -1 is returned to indicate the absence of the target element.

9. In the code's main method, a sorted array arr and a target element value target are declared.

10. The binarySearch method is called with arr and target as arguments, and the returned index is stored in the result variable.

11. Finally, the result is printed to the console, indicating the index of the target element in the array or -1 if it is not present.

The time complexity of the binary search algorithm is O(log n) as it efficiently halves the search range in each iteration, making it suitable for large arrays.