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.

An Iterative Binary Search Example using Java:

public static<E extends Comparable<? super E>> E searchIterative(E[] array, E data) {
    if(data == null || array == null) return null;
    int low = 0;
    int high = array.length -1;

    while(low <= high){
        int mid = low + ((high - low)/2);

        int comp = array[mid].compareTo(data);
        if(comp > 0) high = mid - 1;
        else if(comp < 0) low = mid + 1;
        else return data;
    }
    return null;
}

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.

The method above performs these steps:

1. Checks to see if the list of elements or item to search for are null. If they are, return null.
2. Creates “high” and “low” indexes, which to start are just the first and last elements of the array.
3. Enters a loop in which the updated midpoint, high, and low indexes are determined.
4. Continues 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.