Binary search

Binary search is a Search algorithm suitable for searching a set of sorted data for a particular value.

In its most simple form, binary search takes a sorted list of data, and a value to be searched for. It returns success if the value is found in the data, and failure if the value is not found in the data.

Input is a list L and a value V. L[x] denotes the xth element in L, which consists of N values, L[1], L[2], ..., L[N]. L[x] <= L[x+1], for all list elements between 1 and N-1.

Return success if at least one of the elements of L is equal to V, otherwise return failure

 function binary-search(L,V)
   set start = 1
   set end = N
   repeat while start <= end
     set middle = (start + end) div 2
     if V = L[middle]
       return success    
     else-if V < L[middle]
       set end = middle - 1 
     else-if (V > L[middle])
       set start = middle + 1
     end-if
   end-repeat
   return failure
 end-function

 Notes: 
  div is integer division (discard any remainder)

Binary search executes in O(log n). Specifically, 1 + log₂ N iterations are needed to return an answer. It can be implemented using recursion or iteration?, although in many languages it is more elegantly expressed recursively.

An example of binary search in action is a simple guessing game in which a player has to guess a positive integer selected by another player between 1 and N, using only questions answered with yes or no. Supposing N is 16 and the number 11 is selected, the game might proceed as follows.

Is the number greater than 8? (Yes)
Is the number greater than 12? (No)
Is the number greater than 10? (Yes)
Is the number greater than 11? (No)

Therefore, the number must be 11. At most ceiling(log₂ N) questions are required to determine the number, since each question halves the search space. Note that one less question (iteration) is required than for the general algorithm, since the number is constrained to a particular range.

/Talk