Sequential and Binary search with Python

Search algorithms are designed to find specific elements in data structures such as arrays, lists, dictionaries, and others.

Let’s put aside built-in functions available in programming languages, as in the example below:

if x in list_of_elements:
	return True

For the purpose of study, we will code our own algorithms to understand how they work and the best use for each

Sequential search

Imagine a list with n elements and you need to find a specific element in it. In a sequential search, the algorithm passes through each element and checks if it’s the one we are looking for.

list_of_elements = [10, 44, 33, 22, 50, 3, 13, 8, 11, 11, 57, 90, 91]
x = 90 # The element we want to find
for item in list_of_elements:
	if x == item:
		print('Found X')
		return True
print("Couldn't find X")
return False

Exaplaning: In the example above example we have a list (list_of_elements) with 13 numbers on it. We want to find if X (90) is in the list. In the sequential search we are going to loop on each element of the list and check if it is equal to X.

In a small list like that we won’t have any performance issues, but imagine doing that with a big array and/or complex objects with more validations or business rules. It could take many miliseconds or even seconds for each iteration. In an application that runs many times a day it could be crucial, but easily avoidable.

The sequencial search has a time complexity of O(n), which means that the time is directly linked to the list size.

Binary search

In the previous example, we saw that iterating through an entire list is not the most efficient way to search for an element, but with binary search, we can reduce this task to half at each iteration..

There is only one requirement for performing a binary search: the list must be sorted.

Get Fell’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

To start the example, we need to sort the previous list:

list_of_elements = [3, 8, 10, 11, 11, 13, 22, 33, 44, 50, 57, 90, 91]

Once the sorting is done let’s try to find again the number 90.

The binary search consists to use the sorted list from the central element and checking:

• If it is the number we are looking for.
• If the searched number is bigger than middle element, the search continues to the right half of the list.
• If the searched number is less than the middle element, the search continues to the left half of the list.

Let’s see this logic step by step:

In our list the central element is the number 22 (7th element), leaving 6 elements to the left and 6 elements to the right. With that in mind we need to check if the searched element is the one in the middle (22 in this case).

We are searching for the number 90 which is bigger than 22, so the 90 is on the right half of the list and we can discard the entire left half of the list.

The second half is consists of 33, 44, 50, 57, 90, 91. As we have 6 numbers in the list we’re going to consider the 3rd element (50) as the middle. Again we need to compare this middle number with the element we’re looking for. In this case 90 is bigger than 50, which means the 90 isn’t in the left half of this list.

That leave us the right half of the list with the elements 57, 90, 91. We’ll keep doing the same process as before. In this case the middle element of the list is exactly the number we are looking for.

The binary search is a classic example of divide and conquer algorithm e it brings a time complexity of O(log n) which is much more efficient when compared to the sequential search.

Bellow we have an example of binary search made in Python using recursion:

def binary_search(list_of_elements, x):
    # Obtendo o meio da nossa lista
    mid_list = len(list_of_elements) // 2
if len(list_of_elements) == 0:
        return False
    if list_of_elements[mid_list] == x:
        return True
    if x > list_of_elements[mid_list]:
        """"
        Executando novamente a função binary_search
        mas dessa vez passando a metade da direita da lista
        para a função.
        """
        return binary_search(list_of_elements[mid_list + 1:], x)
    if x < list_of_elements[mid_list]:
        """"
        Executando novamente a função binary_search
        mas dessa vez passando a metade da esquerda da lista
        para a função.
        """
        return binary_search(list_of_elements[:mid_list], x)
# Iniciando
list_of_elements = [3, 8, 10, 11, 11, 13, 22, 33, 44, 50, 57, 90, 91]
x = 90
print(binary_search(list_of_elements, x))

To conclude this article, there’s many other search algorithms to study and most of the languages already have functions to abstratic this logic. In any case it is really important to know the basic logic behind the search algorithms.

As this is my first article written in English, and it is not my native language, there may be some incorrect expressions or words. Please let me know in the comments section below if I have failed to make some concepts clear to you all.