Binary Search Algorithm

This algorithm operates on a ordered list of values and uses the order to conduct the search.

Principe

How quickly find the word Doe in a dictionary? If you open the book in the middle you fall on words beginning with the m letter that is in the middle of the dictionary. We see that Doe can not be included in the first half, so we limit the search to the second part, from m to z.
We forget the first half and we do the same reasoning on the second and so forth on each new part, that gradually reduces the list from either the left or the right part to finally reach the page containing the sought word.

The principle of binary search can be generalized to any type of problem provided the objects of the search can form a sequence and it is possible to make a comparison on the order in the sequence.

Implementing the algorithm on a computer is easy with the recursion, but it can also be implemented iteratively.

Recursive algorithm

Generic code (scriptol)

int binarySearch(int value, int starting, int ending)

  if ending < starting return -1
  int mid = (starting + ending)  / 2	
  if A[mid]
  = value 
    return mid
  > value 
    ending = mid - 1
  < value
    starting = mid + 1   
	/if	 
return  binarySearch(value, starting, ending) 
  

The A array is referenced as a global variable that dramatically accelerates the speed of the script, and the variables starting and ending are used to select a portion gradually reduced of the array.

• Full recursive script.
• PHP code.

Iterative algorithm

Generic code (scriptol)

int binarySearch(int value, array A)
	int starting = 0
	int ending = A.size() 
	int mid
	int length
  
	while forever  

		if starting > ending return -1   
 		length = ending - starting 
		
		if length = 0
			if value = A[starting] 	return starting
			return -1 
		/if	 
 		mid = starting + int(length / 2)
		if value 
		< A[mid] :	ending = mid - 1
		> A[mid] :	starting = mid + 1
		else
			return mid
		/if
	/while
return -1
  

The example uses the array as a parameter of the function, but we might as well use it as a global variable as in the recursive algorithm.

• Full iterative script.
• PHP code.

Application to an array of strings

Code of the algorithm:

int binarySearch(text value, int starting, int ending)
  if ending < starting return -1
  int mid = (starting + ending)  / 2

  int result = strcmp(value, A[mid])  	
  if result
  = 0 
    return mid
  < 0 
	ending = mid - 1
  > 0
    starting = mid + 1   
  /if
		 
return  binarySearch(value, starting, ending) 

Only the function of comparison has changed. The function strcmp returns 0 when strings are identical, a number fewer than 0 if the first is before the second and greater than 0 otherwise.

• Complete source code.
• PHP code.

Performances and choice of algorithm

The binary search is much faster than a linear search that compares the elements successively in the list, unless the list is very short or if the item sought is at the top of the list, which is not normally predictable.

Languages

The C++ language provides a function in the STL library: binary_search.
The framework .NET has similar functions in the basic library (System.Array).
Adapting the generic code above should not be a problem in other programming languages.