Web Development Articles

The Binary Search searches for an element in an ordered list. The algorithm initiates by visiting the middle of the list and comparing the middle value to the desired result or “target”. This target is typically specified by input from a user before the algorithm is executed. If the target is higher than the middle value, the bottom half of the list is discarded from the search. Alternatively, if the desired value is lower than the middle value, then the upper half of the list is discarded. This process is repeated until the desired search result is found. If the current middle value equals the search target, then the algorithm will terminate as it has accomplished its purpose and found the location of the target.

The Binary Search is a much more effective search method than a sequential or linear search, for example, especially for large sets of data. An ideal application of the Binary Search would be searching for a record in an ordered list of employees which are kept in order by the employees’ unique ID. With this in mind, the Binary Search has the disadvantage of only being able to operate on an ordered set of data. Even so, there are many simple ways to order a list or set of data, and once sorted, the Binary Search can offer a very swift method of searching.

The time complexity of the Binary Search is O(log(N)) which means it is a logarithmic algorithm. This means that as the input data increases in size, the algorithm gets more efficient. This efficiency is in terms of the relationship between its average execution time and the input data size. For large sets of data (this enables successful asymptotic analysis of the algorithm), if the input list size doubles (2N), the execution time will go from a factor of log(N) to log(2N) which is a lot less than double.

A Java implementation of the Binary Search is shown below:

/**
 * The class BinarySearch
 *
 * @author  Jon Jackson
 */
public class BinarySearch
{
  // instance variables
  private int first, middle, last;
  private int[] list;

  /**
   * The main search method.
   * 
   * @param list - the list to be sorted
   * @param searchTarget - the value to be searched for
   * 
   * @return middle or 0 - the location of the requested element is returned
   * if it exists in the list, otherwise 0 is returned
   */
  public int search(int[] list, int searchTarget)
  {
    last = list.length - 1;
    first = 0;
    // while there are still elements to search through
    while (first <= last)
    {
      middle = (first + last) / 2;
      // if current middle value is the search target
      if (list[middle] == searchTarget)
      {
        return middle;
      }
      // if current middle value is less than the search target
      else if (list[middle] < searchTarget)
      {
        first = middle + 1;
      }
      // if current middle value is larger than the search target
      else
      {
        last = middle - 1;
      }
    }
    // return 0 if search target not found
    return 0;
  }
}

Check out the Computation and Algorithms section of the Computing Students website for information on some other search and sort algorithms. Another useful resource: Algorithms & Data Structures.