How to Implement the Binary Search Algorithm in Python

Binary search is a well-known computer science algorithm you can implement in many languages including Python.

It is an algorithm that allows finding elements in a sorted array. It is frequently brought up in programming competitions and technical interviews.

You should always use existing libraries when performing binary search in Python or any other language. We are making an exception in this tutorial so you can understand how binary search works.

To go through this tutorial you should have a basic knowledge of Python constructs and data types like tuples, lists, and dictionaries.

Let’s start!

What Is Binary Search?

The Binary search algorithm allows finding elements in a sorted array. It is more efficient than other algorithms like linear search.

For example, let’s say you have an array of ten thousand elements and you want to find the index of a specific element in the array.

Binary Search provides a very fast way to find the index of the element you want to search.

Let’s see the steps to implement binary search.

• The first step is to sort the array. Sorting means arranging the elements of the array in a certain order.
• Split the array into two halves by identifying the index of the middle element in the array.
• Compare the middle element with the value you want to find. If the element matches, then return the index of that element.
• If the value you want to find is greater than the middle element, then take the second half of the array and split it again into two halves.
• If the value you want to find is lower than the middle element, then take the first half of the array and split it into two halves.
• The process continues until the middle element matches the value you want to find.

Firstly, let’s understand what sorted means by looking at the pictures below: