Article - Debugging Binary Search

The reason the extra base is important is that if you do include the midpoint there are times when your code will never check only a single element because the midpoint will not change (take a moment to think about when this is the case before reading on).

Now, let's say that you have the following array:

a[0] = 1 
a[1] = 4 
a[2] = 7 
a[3] = 9

and you search for an element not in the array: say 22. First, the code will check the midpoint: (0+3)/2 = 1. a[1] < 22, so the code will then search the subarray from 1 to 3. The midpoint of this subarray is (1+3)/2 = 2. a[2] < 22, so the code will then search the subarray from 2 to 3. The midpoint of this subarray is (2 + 3)/2 = 2. a[2] < 22, so we'll search the subarray from 2 to 3 again. But this is the same thing we just did! Infinite recursion ensues. (Until we run out of stack space.)

This problem leads to the code searching in a 2 element subarray infinitely many times; and it will only affect 2 element subarrays because computing the midpoint on anything large than 2 elements results in a new midpoint (since the sum of the two array indexes must be at least 2*midpoint + 2, and that extra +2 when divided by two results in at least an addition of one to the previous midpoint). My friend's redundant base case would correctly handle this is the case because it explicitly checks for a 2 element array.