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:**

- Take the midpoint between the smallest and largest elements.
- 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.

- 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:**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
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:**

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