Tech Blog of Jegrami's

You are at a supermarket to get some chocolate bars. The market is large, with many aisles displaying products of different types, shapes, and sizes. You can find what you are looking for by checking every single item in every category of every section. This is called simple search (or linear search).

For a small list of items, simply going through them one by one to find what you're looking for is the reasonable way to go. But for a large group of things, such as goods in a supermarket, running a simple search would consume a lot of energy and waste a lot of time.

You need a better way.

This article is a non-technical introduction to the concept of binary search algorithms. You’ll learn what binary search is and how it compares to simple search. You’ll also learn how to implement the technique in code by writing a simple binary search algorithm in Python!

Back to our supermarket example.

We know that products in a supermarket are often organized into categories, like “Canned Goods”, “Confectioneries”, “Fresh Produce”, etc. So the smarter way to find chocolate bars would be to narrow down your search by going to the specific category in which you would expect to find chocolates, such as the section labeled “Confectioneries”, and begin your search from there. This is similar to how binary search works.

Binary search is an algorithm. An algorithm is a series of steps a computer can follow to perform a task. The task could be a simple one like adding two numbers or a complex one like finding the shortest possible path to a group of five cities in different geolocations.

A binary search algorithm enables you to quickly find the position of something in a sorted list of things by repeatedly dividing the list in the middle, narrowing down the possible location of the target item with each split, until the item is found or the list is exhausted.

Our supermarket technique isn’t an exact implementation of a binary search algorithm, but the underlying principle is the same: eliminate irrelevant options to get to your target item faster.

The guessing game

One practical application of the binary search technique is in the popular guessing game. Here is an example.

I’m thinking of a number between 1 and 10. Your goal is to guess the number in the fewest tries possible, much like the Wordle game. With each attempt, I'll tell you whether your guess was too low, too high, or correct.

Let’s assume my secret number is 9. You could try to guess it by following the simple search approach, considering every single number from 1 through 10, like this:

But wait, that took you nine tries! In Wordle, you’d have run out of guesses before you got the number correctly.

Now what if you applied a binary search approach? You know the size of the list is 10, and you also know the list is sorted (binary search works only on sorted lists), so you’d start your guess from the middle:

You got the answer in 3 tries, enough to win a Wordle game! That’s four steps fewer than the linear search approach.

This may not seem much at first. But the difference in steps between linear search and binary search increases significantly as the input size grows. That is, as the list gets larger, binary search becomes much faster compared with linear search; the gap in efficiency between the two methods widens considerably.

Consider this next example:

At the time of this writing, Spotify has about 11 million artists on its platform. Imagine you want to search for a particular artist by name. Using the linear search technique, you'd have to look at every name in the database, from first to last. That's 11 million lookups, assuming the target name is the last entry in the database. With a binary search algorithm, however, it would take only about 23 lookups! Note how the difference in performance has widened dramatically as we moved from 10 items to 11 million.

But how did I know a binary search algorithm would need only about 23 steps to search an entire list of 11 million names? I explain how in the next section.

Big O notation

To measure the speed (a.k.a., runtime) of an algorithm, computer scientists like to use a technique called Big O notation.

Big O notation is simply a way to tell how much slower an algorithm would run if the size of the data it's dealing with grows. In the above examples, we saw how a simple search algorithm went quickly from 9 steps (when the dataset was just 10 numbers) to 11 million steps (when the dataset increased to 11 million names) , while a binary search algorithm went from 3 steps to 23 steps with the same data sizes. This makes binary search the better technique, especially when the list is large and sorted, because the growth of the data does not affect the speed of the algorithm very much.

There are several Big O runtimes (you can check out this comprehensive Big O cheatsheet), but for the sake of simplicity,
we'll focus only on the two that are most relevant to this article:

• O(n) — where n is the size of the list
• O(log n) — where n is the size of the list

O(n)

When an algorithm has an O(n) runtime, we say that it runs in linear time, or n length of time. This means that, as the data size (n) grows, the amount of time the algorithm takes to run also grows linearly. (The 'O' in the formula is just the symbol describing the notation.)

So if the list is 10 items long, an algorithm with this runtime might take 10 steps to complete a search on it. If the list grows to 11 million, it might then take 11 million steps. The simple search technique, introduced at the beginning of this article, is an example.

O(log n)

Unlike simple search, an algorithm with O(log n) runtime is said to run in logarithmic time. And the binary search algorithm is an example. But what does it mean for an algorithm to run in O(log n) time? More on that in a bit.

Before I proceed, two points about logarithms:

First, in Big O, log is always understood to be in base2, so the small ₂ is sometimes left out in the expression. When you see log n, you should interpret it as log2n (i.e., log base two of n).

Second, think of logarithms as the opposite of exponents. For example, the expression two exponent three (23), in logarithm, would be written as log base two of eight (log 8). Why? Because 23 simply means 2*2*2, which is equal to 8. Converting log 8 back to its exponent can be done by simply asking the question, How many time do I have to multiply 2 by itself to get 8 ? (Remember, it always in base2.) The answer is three times (2*2*2 = 8). That gives you the exponent 23. Logarithms are like the "undo" button for exponents, and vice versa.

Now, going back to our Spotify artist list example. We know that a binary search algorithm runs in logarithmic time. We also know that the Spotify artists databse has 11 million entries. And, based on our knowledge from the second point on logarithms above, log 11,000,000 = 23 (2 multiplied by itself 23 times gives you 11 million.

So a binary search algorithm would run a complete search on a sorted list of 11 million names in approximately 23 lookups.

Big O helps us compare algorithms to understand how they perform as the data they handle gets larger. It helps us make better decisions on which algorithm to use for specific use cases because, using Big O notation, we can predict how their performance will be impacted as their input size grows.

Writing your first binary search algorithm in Python

Now that you understand what binary search is, how it compares to linear search,
and how computer scientist and software engineers measure the performance of algorithms, you’re ready to write your first binary search algorithm.

To follow the code example in this section, you’ll need to have Python and a code editor installed. Get the latest version of Python for your operating system on the official website. For a code editor, VS Code is a popular choice. It’s free, lightweight, and feature-rich. Get it here. The rest of this tutorial assumes you have Python 3.13 and VS Code installed.

A basic binary search algorithm accepts two arguments: a sorted list and an item to search for in that list. If the item is on the list, the algorithm would return its index (i.e., its position relative to other items on the list). If the item is not on the list, the function would return None.

So let's start coding. Open your code editor, create a new file, and name it binary_search.py.

We’ll start by defining the binary search function we just described above using the def keyword:

The code above defines a function called binary_search that expects two arguments: a sorted list and the item you want to search for in that list. Once these two arguments are supplied, the function will calculate and print out the location (index) of the item you’re looking for. The comment enclosed by ''' ''' is the function documentation (a.k.a, docstring). It describes the function and what it does. The pass keyword is a placeholder for code we'll add later.

In binary search, knowing the exact length of the list is important. So the next step is to set the positions of the first and last items on the list you're working with. This will help you keep track of your search range as you traverse the list:

The position of the last item in a sorted list is simply the length of the list minus 1. This is because, in programming, we use zero-based indexing, where the first item in a sequence is assigned the index 0, the second takes index 1, and so on. So, in a sorted list of 10 items, the last item sits at index 9.

Here's the remaining body of code for the binary search algorithm:

A lot of interesting things are going on in the code above. Let’s take it line by line.

After defining the function and marking the positions of the first and last items, we proceed to traverse the list looking for the target item.

The first line initializes a while loop that runs as long as the starting index (first_item) is less than or equal to the ending index (last_item). This loop ensures that the search continues until the target item is found or until we reach the last item and exhaust the list. The next line calculates the position of the current middle item by adding the first and last indexes and dividing by 2. The // operator, called floor division in Python, ensures that the result of the division is a single integer value, not a decimal. For example, 5 // 2 returns 2, whereas 5 / 2 returns 2.5. We want a single, definite position. We don't want a "point something".

Here, the middle item of sorted_list is retrieved and assigned to the name guess. This is our current candidate for the target item. This is the same as what we did in the guessing game example using binary search, where we picked 5, the middle item, as our first guess.

Here we're are checking to see whether our first guess matches the target item. If yes, the function returns middle_item, which should be the index of item insorted_list. If you want the code to return the item itself, not its position on the list, all you have to do is change the return value from middle_item to item. So the code would now read:

The next step:

If the number we picked is greater than the target number (guess > item), it means the number we're looking for must be in the lower half of our list. So we narrow our search range to the lower half by bringing our current ending index (last_item) back one position less than the middle, effectively cutting the list in half. But if our guess is less than the target (guess < item), the code also moves the starting index (first_item) forward one position greater than the current middle, discarding the lower half.

For example, assuming our list has 10 items. The target item is 3, but our first guess was 5, which is higher than the target. Invariably, every item after 5 (i.e., 6, 7, 8, and 9) would also be higher than our target and therefore irrelevant to our search. We discard the irrelevant half of the list (5 – 9) by updating the position of last_item to be middle_item minus 1. That would be 5 - 1, which is 4. So our new list now starts at 0 and ends at 4. If our first guess was lower than the target, the algorithm would do the same operation in reverse. Our new list would then start at 5 and end at 9.

The last line:

If the while loop completes without finding the target item, the function returns None. This indicates that the item is not present in the list.

Here's the complete code:

Let's run the code to see if it works. We’ll test it on two sorted lists: a list of numbers and a list of desserts sorted in alphabetical order:

If everything goes well, you should see results similar to the examples above. The algorithm returns the positions of the items you specify in the first and second print calls. The number 77 is at index 6 of the list numbers, which is why the function returns 6. The same goes for 'ice cream', which is at position 3 of the list desserts. The third and fourth print calls both returnNone because 90 is not in numbers nor is 'cheesecake' in desserts.

That's it! You have successfully implemented a binary search algorithm in Python. Although it’s tested here on a small list of items, this algorithm will work perfectly even if the list is one billion items!

Don’t stop here. There are many more powerful and important algorithms to learn. This is your first step into mastering skills that are useful for everyday problem-solving. I’m also learning and loving it. Join me!