Recursive Binary Search and the Base Case

Solution

Without it, a search for an absent value eventually reaches a range that holds no elements, such as low = 1, high = 0, but the method still computes a mid from those bounds, compares against an element outside the range, and calls itself again with the identical bounds. This means the recursion never stops, and the stack grows until it overflows. With the base case in place, the recursion always reaches it: every call sets low to mid + 1 or high to mid - 1, and mid always lies between low and high, so the gap between low and high shrinks on every call. The gap cannot shrink forever, so low eventually passes high.

Exercise

Implement the recursive binarySearch below. The public method takes just the array and the target; the private helper takes the bounds.

public static boolean binarySearch(int[] arr, int target) {
  // TODO: implement this method
}

private static boolean binarySearch(int[] arr, int target, int low, int high) {
  // TODO: implement this method
}

Solution

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);
  }
}

Solution

low and high are bookkeeping the recursion needs to describe the current range, not something a client should choose. If they were public parameters, a client could pass bounds that do not cover the array and get a crash or a wrong answer. Hiding them behind a public method that always starts the private helper with 0 and arr.length - 1 removes that possibility, and it also hides whether the search is implemented recursively or with a loop, so one can be swapped for the other without changing any client code.