The Binary Search algorithm searches for an item in an ordered list. The algorithm initiates by visiting the middle of the list and comparing the middle value to the desired result. If the desired result is higher than the middle value the bottom half of the list is discarded. 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 result is found.

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.

Binary Search Pseudocode

Input: ordered list and element to be searched for (the search target)
Output: location of search target or 0 if target is not found

Algorithm binarySearch(list[], searchTarget)
last <-- length(list[])
first <-- 1
// while there are still elements to be searched through
while first = last do
	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
	end if
end while
// return 0 if search target not found
return 0

Search for "Binary Search" on: Google | Kelkoo | Amazon | eBay (UK) | eBay (US)

Search for "Binary Search" on the rest of Computing Students: Binary Search