Question 35 Lesson • 9 min read

Question 35 - Iterative binarySearch of 1D int array (focus: purpose, speed, accuracy):

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

    // Continue the search as long as the start index is less than or equal to the end index
    while (start <= end) {
        // Calculate the midpoint of the current search range
        int mid = (start + end) / 2;

        // If the target is less than the value at the midpoint, adjust the end index
        if (target < data[mid]) {
            end = mid - 1;
        }
        // If the target is greater than the value at the midpoint, adjust the start index
        else if (target > data[mid]) {
            start = mid + 1;
        }
        // If the target is equal to the value at the midpoint, return the index
        else {
            return mid;
        }
    }

    // If the target is not found, return -1
    return -1;
}

If you were to plug in the provided values:

int[] values = {1, 2, 3, 4, 5, 8, 8, 8};
int target = 8;

// Calling the binarySearch method and storing the result in the 'result' variable
int result = binarySearch(values, target);

Here’s a breakdown of the process:

1. Initially, the search range is set with start = 0 and end = 7 (length of the array - 1).
2. In the first iteration, the midpoint mid is calculated as (0 + 7) / 2 = 3. Since the target (8) is greater than data[3] (4), the search continues in the right half of the array, and start is updated to 4.
3. In the second iteration, the midpoint is calculated as (4 + 7) / 2 = 5. Here, the target (8) is equal to data[5], so the method returns 5 as the index where the target is found.

As a result, the value returned by the call binarySearch(values, target) is 5. This indicates that the target value 8 is found at index 5 in the given array values.

Here’s an example to try:

Fill in the blanks in the following Java code to declare an array of characters and choose a target character for a binary search. Once the blanks are filled, run the code to perform the binary search and determine whether the target character is present in the array. If found, print the index; otherwise, print a message indicating that the target character was not found.

public class CharBinarySearchExample {

    public static int charBinarySearch(char[] data, char target) {
        int start = 0;
        int end = data.length - 1;

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

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

        return -1;
    }

    public static void main(String[] args) {
        // Fill in the blank: Declare an array of characters (similar to the previous example)
        char[] characters = ____;

        // Fill in the blank: Choose a target character to search for in the array
        char targetChar = ____;

        int result = charBinarySearch(characters, targetChar);

        if (result != -1) {
            System.out.println("Target character '" + targetChar + "' found at index " + result);
        } else {
            System.out.println("Target character '" + targetChar + "' not found in the array.");
        }
    }
}

Your task is to fill in the blanks with appropriate values for the array of characters (characters) and the target character (targetChar). After filling in the blanks, you can run the code to see the results of the binary search.