Overview

The first mention of the binary search algorithm was in 1946 by John Mauchly. The algorithm was further formalized and generalized by Derrick Henry Lehmer in 1960. It has grown to become one of the quintessential algorithms in all of computer science and its existence has allowed computing to reach the levels it has today.

Concept

The concept of binary search is pretty easy to understand. The steps to find a value include:
1. Pick the middle index into a sorted array and evaluate the value. If the value is less than the desired value, eliminate the upper half of the array from the search. If the value is greater than the desired value, eliminate the lower half of the array from the search.
2. Repeat step 1 for either the lower half or upper half of the original sorted array until the value is either found or not found.

Algorithmic Complexity

Big-O

Algorithm	Data Structure	Time Complexity - Average	Time Complexity - Worst	Space Complexity - Worst
Depth First Search	Graph of |V| vertices and |E| edges	-	O(|E|+|V|)	O(|V|)

Implementation

Java Implementation

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * Binary Search algorithm implementation
 * 
 * www.algorithmiccomplexity.com
 */
public class BinarySearch {
	
	public static boolean binarySearch(final List searchList, final int value)
	{
		if(searchList == null || searchList.isEmpty())
		{
			return false;
		}
		
		int pivot = searchList.get(searchList.size() / 2);

		if(value == pivot)
		{
			return true;
		}
		else if ( value < pivot)
		{
			return binarySearch(searchList.subList(0, searchList.size() / 2), value);
		}
		else
		{
			return binarySearch(searchList.subList(searchList.size() /  2 + 1, searchList.size()), value);
		}
	}
	
	/**
	 * Test driver for the binary search algorithm.
	 * 
	 * @param args Command line arguments {@code null}.
	 */
	public static void main(String[] args)
	{
		List searchList = new ArrayList<>();
		searchList.add(10);
		searchList.add(5);
		searchList.add(3);
		searchList.add(7);
		searchList.add(1);
		searchList.add(8);
		searchList.add(8);
		searchList.add(0);
		searchList.add(6);
		searchList.add(5);
		
		Collections.sort(searchList);
		
		boolean found  = BinarySearch.binarySearch(searchList, 5);
		System.out.println("Searching for value: " + 5 + " in list " + searchList + " result: " + found);
		found  = BinarySearch.binarySearch(searchList, 4);
		System.out.println("Searching for value: " + 4 + " in list " + searchList + " result: " + found);
	}
}

 

References

Wikipedia: Binary search algorithm