AP Computer Science Exam Question - Binary Search

Write a Java method called binarySearch that takes in two parameters: an integer array arr and an integer value target. The arr parameter represents a sorted array of integers in ascending order, and the target parameter represents the value that we want to search for within the array. The method should return the index of the target value if it exists in the array, otherwise return -1.

Assume that the arr parameter will always be non-null and that the length of the array will always be greater than 0.

Your task is to implement the binarySearch method using the binary search algorithm.

Signature:

public static int binarySearch(int[] arr, int target)

Example:

int[] arr = {2, 4, 5, 8, 10};
int target = 8;
int index = binarySearch(arr, target);
System.out.println(index); // Output: 3

Explanation:

The given array arr is {2, 4, 5, 8, 10} and the target value is 8.

The binary search algorithm works by comparing the target value with the middle element of the array. If the middle element is equal to the target, we have found the value and return its index. If the middle element is greater than the target, we update the end index to be the middle index - 1 and repeat the process on the left half of the array. If the middle element is less than the target, we update the start index to be the middle index + 1 and repeat the process on the right half of the array.

1. Initialize two pointers, start and end, to represent the range of the search within the array. Initially, start is set to the first index (0) and end is set to the last index (arr.length - 1).

2. Start a while loop that continues as long as start is less than or equal to end.

3. Inside the while loop, calculate the mid index by finding the average of the start and end indices: int mid = (start + end) / 2.

4. Check if the target value is equal to the element at the mid index: if (arr[mid] == target), if true, return mid.

5. If the target value is less than the element at the mid index, update end to be mid - 1. This narrows down the search to the left half of the array.

6. If the target value is greater than the element at the mid index, update start to be mid + 1. This narrows down the search to the right half of the array.

7. Repeat steps 3 to 6 until the start index becomes greater than the end index.

8. If the while loop completes without finding the target value, return -1 to indicate that the target is not present in the array.

Here's the implementation of the binarySearch method:

public static int binarySearch(int[] arr, int target) {
    int start = 0;
    int end = arr.length - 1;

    while (start <= end) {
        int mid = (start + end) / 2;

        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] > target) {
            end = mid - 1;
        } else {
            start = mid + 1;
        }
    }

    return -1;
}

The time complexity of the binary search algorithm is O(log n), where n is the size of the input array. This is because the search range is halved in each iteration, resulting in a logarithmic time complexity.