Recursive Binary Search and the Base Case

Solution

The base case is an empty range, low > high, where the method returns without searching further. Without it, the method would either read outside the array or never return. Unless the target is found first, the recursion always reaches the base case: 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.