A binary search algorithm is an algorithm used to search an already sorted list for an element in the list.

The method is analogous to guessing the answer to a number guessing game, where you are provided with a range of numbers and will guess the number in the mind of the host. The host may respond with "higher [number]", "lower [number]" and "yes" (meaning the guess is correct).

The algorithm runs in O(log n) time.

Pseudocode

This inputs a list arr(0 to n-1) and outputs the index of the item if it is found, otherwise -1.

Recursive

binary_search(arr, item)
   binary_search(arr, item, 0, n-1)

binary_search(arr, item, low, high)
   if high < low
      return -1
   middle = (low + high) / 2
   if A at mid > value
      return binary_search(arr, item, low, mid-1)
   else if A at mid < value
      return binary_search(arr, mid+1, high)
   else
      return mid

Non-recursive

binary_search(arr, item)
   low = 0
   high = n-1
   // you may choose whether or not to initialize mid here
   while not high < low  // can be rephrased as low >= high
      mid = (low + high) / 2
      if arr at mid > item
         high = mid - 1
      else if arr at mid < item
         low = mid + 1
      else
         return mid
   return -1