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.

## PseudocodeEdit

This inputs a list `arr(0 to n-1)`

and outputs the index of the item if it is found, otherwise -1.

### RecursiveEdit

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-recursiveEdit

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