# Binary Search Algorithm

Binary Search is an algorithm that finds a given element (or asserts its absence) in a sorted list in logarithmic time.

By “sorted list”, we mean that for every element `a_i`

in a list of `n`

elements, its predecessors are equal or smaller than `a_i`

and its successors are equal or larger than `a_i`

, for every `1 <= i <= n`

.

More exactly, for every element `a_i`

, `1 <= i <= n`

, we can assert that `a_k <= a_i, for 1 <= k <= i`

, and also `a_k >= a_i, for k <= i <= n`

.

By “logarithmic” time, we mean that the number of steps taken to complete the algorithm is roughly proportional to the base-2 logarithm of the length of the sorted list. That means that for a list with the square of the size, it takes double of the time to complete.

## Binary Search Algorithm

Described in a Python code snippet below.

`array`

is a sorted list of length`len(array)`

, with value increasing from lower indexes to higher indexes.`element`

is the element being searched for in the array.`lower`

is the lowest index being considered for the search, inclusive.`upper`

is the highest index being considered for the search, non-inclusive. (`-1`

meaning the length of the list).

# NOTE: we assume `array` to be sorted, and `element` to have `==` and # `<` operators defined. def binary_search(array, element, lower=0, upper=-1): if upper == -1: upper = len(array) # no more elements to be considered, search is finished if upper - lower <= 0: return -1 # sentinel value for not found middle = (upper + lower) // 2 x = array[middle] # found it if element == x: return middle # continue searching to the left if element < x: return binary_search(array, element, lower=lower, upper=middle) # element > x, continue searching to the right return binary_search(array, element, lower=middle+1, upper=upper)