The Base Case

We now have a version of binarySearch that passes low and high bounds, but it is not yet complete. Take our running example array {3, 9, 14, 21, 28, 33, 42, 55} and search for a value that is not present, like 5. The recursion goes like this:

binarySearch(arr, 5, 0, 7)   mid=3  arr[3]=21 > 5   -> search (0, 2)
binarySearch(arr, 5, 0, 2)   mid=1  arr[1]=9 > 5    -> search (0, 0)
binarySearch(arr, 5, 0, 0)   mid=0  arr[0]=3 < 5    -> search (1, 0)
binarySearch(arr, 5, 1, 0)   mid=?

When you call binarySearch(arr, 5, 1, 0), the mid calculation is 1 + (0 - 1) / 2. In Java, integer division truncates toward zero, so (0 - 1) / 2 is 0, which makes mid equal to 1. This means that the method tries to access arr[1] again, so you get:

binarySearch(arr, 5, 1, 0)   mid=1  arr[1]=9 > 5   -> search (1, 0)
binarySearch(arr, 5, 1, 0)   mid=1  arr[1]=9 > 5   -> search (1, 0)
binarySearch(arr, 5, 1, 0)   mid=1  arr[1]=9 > 5   -> search (1, 0)
// never ends..

On the call stack, each of these calls pushes another identical frame. Every call waits for another call with the same arguments. Nothing ever returns, and the stack keeps growing:

        ┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓
top ──▶ ┃ binarySearch(arr, 5, 1, 0)  mid=1  waiting for binarySearch(arr, 5, 1, 0) ┃
        ┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛
        ┌───────────────────────────────────────────────────────────────────────────┐
        │ binarySearch(arr, 5, 1, 0)  mid=1  waiting for binarySearch(arr, 5, 1, 0) │
        ├───────────────────────────────────────────────────────────────────────────┤
        │ binarySearch(arr, 5, 1, 0)  mid=1  waiting for binarySearch(arr, 5, 1, 0) │
        ├───────────────────────────────────────────────────────────────────────────┤
        │ binarySearch(arr, 5, 0, 0)  mid=0  waiting for binarySearch(arr, 5, 1, 0) │
        ├───────────────────────────────────────────────────────────────────────────┤
        │ binarySearch(arr, 5, 0, 2)  mid=1  waiting for binarySearch(arr, 5, 0, 0) │
        ├───────────────────────────────────────────────────────────────────────────┤
        │ binarySearch(arr, 5, 0, 7)  mid=3  waiting for binarySearch(arr, 5, 0, 2) │
        └───────────────────────────────────────────────────────────────────────────┘

The program eventually throws a StackOverflowError. There is no path through this method that returns false, so a search for an absent target never returns.

Look at the call where low is greater than high: binarySearch(arr, 5, 1, 0). Here low is 1 and high is 0. The range from index 1 to index 0 contains no elements at all. That is the case the method never checks for. The method computed a mid for an empty range, which is meaningless, and then compared the target against an element that is not in the range.

So the check we need is low > high, and when it holds we return false, because an empty range contains nothing and therefore does not contain the target.

public static boolean binarySearch(int[] arr, int target, int low, int high) {
  if (low > high) {
    return false;  // empty range: target cannot be present
  }
  int mid = low + (high - low) / 2;
  int cmp = Integer.compare(arr[mid], target);
  if (cmp == 0) {
    return true;  // found it
  } else if (cmp < 0) {
    return binarySearch(arr, target, mid + 1, high);  // search the right half
  } else {
    return binarySearch(arr, target, low, mid - 1);  // search the left half
  }
}

The condition low > high, where the lower bound is greater than the upper bound, is the base case for recursive binary search.

Now let’s check that this really does stop the recursion. Every recursive call either sets low to mid + 1 or sets high to mid - 1, and mid is always at least low and at most high. Either way the gap between low and high gets strictly smaller on every call. low and high are integers, so the gap cannot keep shrinking forever. After enough calls low is greater than high, the base case applies, and false is returned back up through the recursive calls. Run the same trace as before and the last line is now binarySearch(arr, 5, 1, 0) returning false instead of calling itself again.