Searching Half the Array

In the last section we settled on a boolean version of binarySearch with an empty body. Let’s fill it in by starting from the iterative version and taking the loop out:

public static boolean binarySearch(int[] arr, int target) {
  int low = 0;
  int high = arr.length - 1;
  int mid = low + (high - low) / 2;  // middle of the whole array
  int cmp = Integer.compare(arr[mid], target);

  if (cmp == 0) {
    return true;  // found it
  } else if (cmp < 0) {
    // middle is too small; search the right half
  } else {
    // middle is too big; search the left half
  }
}

Let’s focus on the part where we need to search the right half. We can do something like this:

// ...
  } else if (cmp < 0) {
    // middle is too small; search the right half
    int[] rightHalf = Arrays.copyOfRange(arr, mid + 1, arr.length);
    return binarySearch(rightHalf, target);
  } else {
// ...

The code above creates a new array rightHalf that contains the elements from mid + 1 to the end of the original array. (We could have done this by first creating rightHalf and then copying the elements, similar to how we implemented grow in DynamicArray, but Arrays.copyOfRange does that for us in one line.)

We start at mid + 1 rather than at mid because we already compared arr[mid] to the target and it is not equal, so there is no reason to look at it again. We end at arr.length because Arrays.copyOfRange treats the second bound as exclusive, so this takes everything through the last element.

The code then calls binarySearch on this new array. That runs the same algorithm on the right half of the original array, which is what we want. By our definition of recursion, this is a recursive method, because it calls itself on a smaller version of the same problem. The left half works the same way: Arrays.copyOfRange(arr, 0, mid) takes indices 0 through mid - 1, again leaving out mid because we have already checked it. Here is how the whole method looks with both cases:

public static boolean binarySearch(int[] arr, int target) {
  int low = 0;
  int high = arr.length - 1;
  int mid = low + (high - low) / 2;  // middle of the whole array
  int cmp = Integer.compare(arr[mid], target);  // compare arr[mid] to target

  if (cmp == 0) {
    return true;  // found it
  } else if (cmp < 0) {
    // middle is too small; search the right half
    int[] rightHalf = Arrays.copyOfRange(arr, mid + 1, arr.length);
    return binarySearch(rightHalf, target);
  } else {
    // middle is too big; search the left half
    int[] leftHalf = Arrays.copyOfRange(arr, 0, mid);
    return binarySearch(leftHalf, target);
  }
}

But each call copies a whole half into a new array, and that copy has a cost. It allocates memory we do not need, and it reads every element of the half one at a time. Reading every element is exactly the work binary search is meant to avoid. We can do better.