Binary Search Algorithm

A fast way to search a sorted array is to use a binary search. Binary search requires that the collection is already sorted. Binary search checks the element in the middle of the collection. If the search element is equal to that, the search is finished. If the search element is less than the middle element, do a binary search on the first half. If the search element is less than the middle element, do a binary search on second half. Once the searched element is found or the collection is empty then the search is over.

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.

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

Example:

public static boolean contains(int[] a, int key) {

    if (a.length == 0) {

      return false;

    }

    int low = 0;

    int high = a.length-1;

    while(low <= high) {

      int middle = (low+high) /2; 

      if (key> a[middle]){

        low = middle +1;

      } else if (key< a[middle]){

        high = middle -1;

      } else { // The element has been found

        return true; 

      }

    }

    return false;

  }

Another version of a binary search method:

public static int binarySearch(String[] sorted, String key) {
    int first = 0;
    int upto  = sorted.length;
    
    while (first < upto) {
        int mid = (first + upto) / 2;  // Compute mid point.
        if (key.compareTo(sorted[mid]) < 0) {
            upto = mid;       // repeat search in bottom half.
        } else if (key.compareTo(sorted[mid]) > 0) {
            first = mid + 1;  // Repeat search in top half.
        } else {
            return mid;       // Found it. return position
        }
    }
    return -(first + 1);      // Failed to find key
}