# 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.