Question

Directions: Select the choice that best fits each statement. The following question(s) refer to the following information

Consider the following binarySearch method. The method correctly performs a binary search.

public static in binarySearch(int[] data, int target)
{
    int start = 0;
    int end = data.length - 1;
    while (start <= end)
    {
        int mid = (start + end) / 2    /* Calculate midpoint */
        if (target < data[mid])
        {
            end = mid - 1;
        }
        else if (target > data[mid])
        {
            start = mid + 1;
        }
        else
        {
            return mid;
        }
    }
    return -1;
}

Consider the following code segment.

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

What value is returned by the call binarySearch (values, target) ?

  • a. -1
  • b. 3
  • c. 5
  • d. 6
  • e. 8

How to solve

The array values is sorted in ascending order. The target value is 8. The binary search algorithm works by repeatedly dividing the search range in half until the target is found or the search range is empty.

In this case, the algorithm would proceed as follows:

  1. Initial range: start = 0, end = 7
  2. Midpoint (mid): (0 + 7) / 2 = 3 (value at index 3 is 4)
  3. Since the target (8) is greater than 4, the algorithm updates the range: start = mid + 1 = 4, end = 7
  4. Midpoint: (4 + 7) / 2 = 5 (value at index 5 is 8)
  5. The target (8) is equal to the value at index 5. The algorithm returns the index 5.

Therefore, the value returned by the call binarySearch(values, target) is 5, indicating that the target value 8 is found at index 5 in the array.

It is important to note that integer division in Java rounds down to the lowest correct answer. See example below.

int [ ] arr = {0, 1, 2, 3, 4, 5, 6, 7};

int first = 0;
int last = arr.length - 1;
int middle = (first + last) / 2;

System.out.println("First: " + first + " | Last: " + last);
System.out.println("Index: " + middle + " | Value: " + arr[middle] ); 

First: 0 | Last: 7
Index: 3 | Value: 3