The goal is to find a number in a list. How can we achieve such an approach with Python? Doing this the ‘classic way’ is to use a linear search algorithm. But the performance might not be the best if we have a list with thousands of elements. Using the Big-O-Notation, it’s only O(n). So, if you have a lot of elements you should try a binary search algorithm (O(log n)) The idea is to split the list in half and determine whether the number we are looking for is in the left half or in the right half.

Note: There are two ways to accomplish this: You can implement a recursive algorithm or a iterative version. Here I go the iterative way.

Let’s say we have the following list:

MY_LIST = [4, 43, 12, 89, 17, 23, 1, 66, 103]

The first thing we have to do is to sort this list using the sort() method.

MY_LIST.sort()
print(MY_LIST)  # -> [1, 4, 12, 17, 23, 43, 66, 89, 103]

Then follows the iterative implementation of the binary search:

def binary_search(number_list, number):
"""A binary search function

Arguments:
	number_list {list} -- A list with sorted integer values
	number {integer} -- The number we are searching for

Returns:
	integer -- Returns the index of the given number
"""

lower_bound = 0
upper_bound = len(MY_LIST)

while lower_bound < upper_bound:

	# Split the list
	mid_index = lower_bound + (upper_bound - lower_bound) / 2
	mid_index = int(mid_index)

	if number_list[mid_index] == number:
		return mid_index

	# Check if the number we are looking for
	# is in the left or the right half
	elif number_list[mid_index] < number:
		lower_bound = mid_index + 1
	else:
		upper_bound = mid_index

INDEX_VALUE = binary_search(MY_LIST, 89)
print(INDEX_VALUE)  # -> Index 7

It’s a lot of code, but we just needed three steps to find the number.

log2(9) = 3.17

With the linear search, it would have taken eight steps.

Note: The binary search is not always the best way to go, because you have to sort the list, and sorting takes time. So, the combination of sorting and binary search might be slower than using a linear search.