AP Computer Science Exam Question

You are given a sorted list of integers, nums, and a target value, target. Write a method, binarySearch, to implement the binary search algorithm and return the index of the target value in the given list. If the target value is not present in the list, return -1.

The method signature is:

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

Example

Given the sorted list: [2, 4, 6, 8, 10, 12, 14, 16, 18, 20] and the target value: 10, the method should return 4 as 10 is located at index 4 in the list.

Constraints

• The input list nums is sorted in ascending order.
• The length of the input list nums will be between 1 and 10^5.
• The value of each element in nums will be between -10^9 and 10^9.
• The target value target will be between -10^9 and 10^9.

Solution

Here is an implementation of the binarySearch method:

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

Explanation

1. Initialize two pointers, left and right, to the start and end of the list respectively. In this case, left = 0 and right = nums.length - 1.
2. Use a while loop to iteratively compare the middle element of the sublist with the target value.
3. Calculate the middle index, mid, using the formula mid = left + (right - left) / 2. This formula avoids potential integer overflows when using (left + right) / 2.
4. If the middle element equals the target value, return the middle index as the answer.
5. If the middle element is less than the target value, set the left pointer to mid + 1. This narrows the search range to the upper half of the sublist.
6. If the middle element is greater than the target value, set the right pointer to mid - 1. This narrows the search range to the lower half of the sublist.
7. Repeat steps 3-6 until the left pointer exceeds the right pointer, indicating that the target value is not present in the list.
8. If the target value is not found, return -1 to indicate absence.

Note that the while loop condition allows for both odd and even length lists by checking if left <= right instead of left < right.

The complexity of the binary search algorithm is O(log N) where N is the length of the input list. This is because the search space is divided in half with each iteration, resulting in a logarithmic time complexity.