Binary Search in Python

This tutorial will learn how we can apply a binary search algorithm using Python to find an element’s index position in the given list.

Introduction

A binary search is an algorithm to find a particular element in the list. Suppose we have a list of thousand elements, and we need to get an index position of a particular element. We can find the element’s index position very fast using the binary search algorithm.

There are many searching algorithms but the binary search is most popular among them.

The elements in the list must be sorted to apply the binary search algorithm. If elements are not sorted then sort them first.

Let’s understand the concept of binary search.

Concept of Binary Search

In the binary search algorithm, we can find the element position using the following methods.

• Recursive Method
• Iterative Method

The divide and conquer approach technique is followed by the recursive method. In this method, a function is called itself again and again until it found an element in the list.

A set of statements is repeated multiple times to find an element’s index position in the iterative method. The while loop is used for accomplish this task.

Binary search is more effective than the linear search because we don’t need to search each list index. The list must be sorted to achieve the binary search algorithm.

Let’s have a step by step implementation of binary search.

We have a sorted list of elements, and we are looking for the index position of 45.

[12, 24, 32, 39, 45, 50, 54]

So, we are setting two pointers in our list. One pointer is used to denote the smaller value called low and the second pointer is used to denote the highest value called high.

Next, we calculate the value of the middle element in the array.

Now, we will compare the searched element to the mid index value. In this case, 32 is not equal to 45. So we need to do further comparison to find the element.

If the number we are searching equal to the mid. Then return mid otherwise move to the further comparison.

The number to be search is greater than the middle number, we compare the n with the middle element of the elements on the right side of mid and set low to low = mid + 1.

Otherwise, compare the n with the middle element of the elements on the left side of mid and set high to high = mid – 1.

Repeat until the number that we are searching for is found.

Implement a Binary Search in Python

First, we implement a binary search with the iterative method. We will repeat a set of statements and iterate every item of the list. We will find the middle value until the search is complete.

Let’s understand the following program of the iterative method.

Python Implementation

Output:

Element is present at index 4

Explanation:

In the above program –

• We have created a function called binary_search() function which takes two arguments – a list to sorted and a number to be searched.
• We have declared two variables to store the lowest and highest values in the list. The low is assigned initial value to 0, high to len(list1) – 1 and mid as 0.
• Next, we have declared the while loop with the condition that the lowest is equal and smaller than the highest The while loop will iterate if the number has not been found yet.
• In the while loop, we find the mid value and compare the index value to the number we are searching for.
• If the value of the mid-index is smaller than n, we increase the mid value by 1 and assign it to The search moves to the left side.
• Otherwise, decrease the mid value and assign it to the high. The search moves to the right side.
• If the n is equal to the mid value then return mid.
• This will happen until the low is equal and smaller than the high.
• If we reach at the end of the function, then the element is not present in the list. We return -1 to the calling function.

Let’s understand the recursive method of binary search.

Recursive Binary Search

The recursion method can be used in the binary search. In this, we will define a recursive function that keeps calling itself until it meets the condition.

Let’s understand the above program using the recursive function.

Python Program

Output:

Element is present at index 2

Explanation

The above program is similar to the previous program. We declared a recursive function and its base condition. The condition is the lowest value is smaller or equal to the highest value.

• We calculate the middle number as in the last program.
• We have used the if statement to proceed with the binary search.
• If the middle value equal to the number that we are looking for, the middle value is returned.
• If the middle value is less than the value, we are looking then our recursive function binary_search() again and increase the mid value by one and assign to low.
• If the middle value is greater than the value we are looking then our recursive function binary_search() again and decrease the mid value by one and assign it to low.

In the last part, we have written our main program. It is the same as the previous program, but the only difference is that we have passed two parameters in the binary_search() function.

This is because we can’t assign the initial values to the low, high and mid in the recursive function. Every time the recursive is called the value will be reset for those variables. That will give the wrong result.

Complexity

The complexity of the binary search algorithm is O(1) for the best case. This happen if the element that element we are looking find in the first comparison. The O(logn) is the worst and the average case complexity of the binary search. This depends upon the number of searches are conducted to find the element that we are looking for.

Conclusion

A binary search algorithm is the most efficient and fast way to search an element in the list. It skips the unnecessary comparison. As the name suggests, the search is divided into two parts. It focuses on the side of list, which is close to the number that we are searching.

We have discussed both methods to find the index position of the given number.