Binary search algorithm

Binary search is much faster than a linear search that compares 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.

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

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 that follow should not be a problem in other programming languages.

Principe of the algorithm

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 version

Generic code (scriptol):

array A = []

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.

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.

Iterative version

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.