Java Notes: Algorithms: Binary Search

Divide in half

A fast way to search a sorted array is to use a binary search. The idea is to look at the element in the middle. If the key is equal to that, the search is finished. If the key is less than the middle element, do a binary search on the first half. If it's greater, do a binary search of the second half.

Performance

The advantage of a binary search over a linear search is astounding for large numbers. For an array of a million elements, binary search, O(log N), will find the target element with a worst case of only 20 comparisons. Linear search, O(N), on average will take 500,000 comparisons to find the element. Probably the only faster kind of search uses hashing, a topic that isn't covered in these notes.

This performance comes at a price - the array must be sorted first. Because sorting isn't a fast operation, it may not be worth the effort to sort when there are only a few searches.

Example

/** Binary search of sorted array.  Negative value on search failure.
 *  The upperbound index is not included in the search.
 *  This is to be consistent with the way Java in general expresses ranges.
 *  The performance is O(log N).
 *  @param sorted Array of sorted values to be searched.
 *  @param first Index of beginning of range.  First element is a[first].
 *  @param upto  Last element that is searched is sorted[upto-1].
 *  @param key   Value that is being looked for.
 *  @return      Returns index of the first match, or or -insertion_position 
 *               -1 if key is not in the array. This value can easily be
 *               transformed into the position to insert it.
 */
public static int binarySearch(int[] sorted, int first, int upto, int key) {
    
    while (first < upto) {
        int mid = (first + upto) / 2;  // Compute mid point.
        if (key < sorted[mid]) {
            upto = mid;     // repeat search in bottom half.
        } else if (key > sorted[mid]) {
            first = mid + 1;  // Repea