Binary Search Algorithm

2022-04-02

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)