Binary Search is a classic algorithm used to find an item in an ordered list/array of items. This list/array of items must be ordered for binary search to work.

The basic idea of Binary Search is to:

1. Take the midpoint between the smallest and largest elements.
2. Determine if item being searched for is smaller or larger than the item at the midpoint.
   • If smaller than the midpoint, consider the largest element moving forward as the midpoint – 1.
   • If larger than the midpoint, consider the smallest element moving forward as the midpoint + 1.
3. Perform steps 1 and 2 while updating smallest and largest points until the desired element is found, or the entire list has been searched.

A Recursive Binary Search Example using Java:

public static<E extends Comparable<? super E>> E searchRecursive(E[] array, E data, int low, int high){
        if(data == null || array == null) return null;
        if(high < low) return null;

        int mid = (low + (high - low)/2);
        int comp = array[mid].compareTo(data);

        if(comp > 0) {
            high = mid - 1;
            searchRecursive(array, data, low, high);
        }
        else if (comp < 0) {
            low = mid + 1;
            searchRecursive(array, data, low, high);
        }

        return data;
    }
}

The method above accepts an array of elements and item the to search for. Both objects must be/contain type E (or a super type of E) which can be any class that, implements the Comparable interface. This ensures that the objects passed to the method can be compared to one another correctly. This method also requires the “high” and “low” indexes used to determine which part of the array to search.

The method above performs these steps:

1. Check to see if the array of elements or item to search for are null. If they are, return null.
2. Enter a loop in which the a midpoint, high, and low indexes are determined.
3. If new midpoint in loop iteration does not equal value being searched for, recursively call the method again, with the updated high and low indexes.
4. Continue in loop until the value searched for is found, or until the entire array has been searched.

A fantastic, more detailed explanation of binary search is available for Khan Academy here.