Passing the Bounds

The copying version creates a new array for the left or right half on every recursive call, and we would like to stop doing that. Think back to the iterative version. It never copies anything. It keeps the original array and uses two indices, low and high, to say which part of the array is still being searched. We want the recursive version to do the same.

The problem is that the recursive call needs somewhere to put those two indices. In the iterative version they are local variables, and the loop updates them. In the recursive version there is no loop, so the only way to pass them to the next call is to make them parameters. Let’s do that:

public static boolean binarySearch(int[] arr, int target, int low, int high) {
  int mid = low + (high - low) / 2;
  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
    return binarySearch(arr, target, mid + 1, high);
  } else {
    // middle is too big; search the left half
    return binarySearch(arr, target, low, mid - 1);
  }
}

The recursive calls now pass arr straight through. An array in Java is a reference type, so passing arr passes a reference to the one array that already exists. No copy is made, no matter how many calls we end up with. The only things that change from one call to the next are low and high. They say which part of that one array the call is responsible for.

Any client that wants to search the whole array can call this method with low = 0 and high = arr.length - 1:

int[] numbers = {3, 9, 14, 21, 28, 33, 42, 55};
int target = 14;
boolean found = binarySearch(numbers, target, 0, numbers.length - 1);
System.out.println("Target found: " + found);

So this version no longer copies. It is still not correct. Try it on a value that is not in the array and see what happens.