A Helper for Binary Search

Let’s overload the binarySearch method. We can have a public method that takes just the array and target, and then it calls a private helper method that also takes the low and high indices as parameters. Here is how that would look:

public static boolean binarySearch(int[] arr, int target) {
  return binarySearch(arr, target, 0, arr.length - 1);
}

private static boolean binarySearch(int[] arr, int target, int low, int high) {
  if (low > high) {
    return false;
  }
  int mid = low + (high - low) / 2;
  int cmp = Integer.compare(arr[mid], target);
  if (cmp == 0) {
    return true;
  } else if (cmp < 0) {
    return binarySearch(arr, target, mid + 1, high);
  } else {
    return binarySearch(arr, target, low, mid - 1);
  }
}

The client now calls binarySearch(arr, target) and does not pass the bounds, which are internal details of the method.

Back when we first wrote the recursive version, we changed the return type from the index to a boolean, because at the time each recursive call worked on a copied half of the array, and translating an index in that copy back into an index of the original array was extra bookkeeping. That is no longer true here. low and high index into the one shared array, the same array the client passed in, so there is nothing left to translate. We could just as well have binarySearch return the index of the target, or -1 if it is not present, matching the iterative version.