Breder.org Software and Computer Engineering

# 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)```