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.
This inputs a list
arr(0 to n-1) and outputs the index of the item if it is found, otherwise -1.
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
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