Learn Python – Binary Search in Python- Basic and advance

This tutorial will learn how we can practice 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 discover a specific factor in the list. Suppose we have a list of thousand elements, and we want to get an index role of a specific element. We can locate the element’s index function very fast using the binary search algorithm.

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

The factors in the list must be sorted to observe the binary search algorithm. If factors are now not sorted then kind them first.

Let’s understand the concept of binary search.

Concept of Binary Search

In the binary search algorithm, we can discover the aspect function the usage of the following methods.

Recursive Method

Iterative Method

The divide and triumph over method method is observed through the recursive method. In this method, a feature is known as itself again and once more until it observed an aspect in the list.

A set of statements is repeated more than one times to locate an element’s index function in the iterative method. The while loop is used for accomplish this task.

Binary search is extra high quality than the linear search due to the fact we don’t want to search every list index. The listing ought to be sorted to obtain the binary search algorithm.

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

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

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

So, we are putting two pointers in our list. One pointer is used to denote the smaller cost called low and the second pointer is used to denote the highest price referred to as high.

Next, we calculate the price of the middle component in the array.

mid = (low+high)/2  
Here, the low is 0 and the high is 7.  
mid = (0+7)/2  
mid = 3 (Integer)  

Now, we will compare the searched element to the mid index value. In this case, 32 is now not equal to 45 So we want to do in addition assessment to find the element.

If the variety we are searching equal to the mid. Then return mid otherwise go to the further comparison.

The wide variety to be search is higher than the middle number, we evaluate the n with the center factor of the elements on the right aspect of mid and set low to low = mid + 1.

Otherwise, evaluate the n with the center element of the elements on the left side of mid and set excessive to excessive = mid – 1.

Repeat till the variety that we are looking out for is found.

Implement a Binary Search in Python

First, we enforce a binary search with the iterative method. We will repeat a set of statements and iterate each item of the list. We will locate the center fee till the search is complete.

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

Python Implementation

# Iterative Binary Search Function method Python Implementation  
# It returns index of n in given list1 if present,   
# else returns -1   
def binary_search(list1, n):  
    low = 0  
    high = len(list1) - 1  
    mid = 0  
  
    while low <= high:  
        # for get integer result   
        mid = (high + low) // 2  
  
        # Check if n is present at mid   
        if list1[mid] < n:  
            low = mid + 1  
  
        # If n is greater, compare to the right of mid   
        elif list1[mid] > n:  
            high = mid - 1  
  
        # If n is smaller, compared to the left of mid  
        else:  
            return mid  
  
            # element was not present in the list, return -1  
    return -1  
  
  
# Initial list1  
list1 = [12, 24, 32, 39, 45, 50, 54]  
n = 45  
  
# Function call   
result = binary_search(list1, n)  
  
if result != -1:  
    print("Element is present at index", str(result))  
else:  
    print("Element is not present in list1")  

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 approach of binary search.

Recursive Binary Search

The recursion method can be used in the binary search. In this, we will outline a recursive characteristic that maintains calling itself till it meets the condition.

Let’s recognize the above application the use of the recursive function.

Python Program

# Python program for recursive binary search.  
# Returns index position of n in list1 if present, otherwise -1  
def binary_search(list1, low, high, n):   
  
   # Check base case for the recursive function  
   if low <= high:  
  
      mid = (low + high) // 2  
  
      # If element is available at the middle itself then return the its index  
      if list1[mid] == n:   
         return mid   
  
      # If the element is smaller than mid value, then search moves  
      # left sublist1  
      elif list1[mid] > n:   
         return binary_search(list1, low, mid - 1, n)   
  
      # Else the search moves to the right sublist1  
      else:   
         return binary_search(list1, mid + 1, high, n)   
  
   else:   
      # Element is not available in the list1  
      return -1  
  
# Test list1ay   
list1 = [12, 24, 32, 39, 45, 50, 54]  
n = 32  
  
# Function call   
res = binary_search(list1, 0, len(list1)-1, n)   
  
if res != -1:   
   print("Element is present at index", str(res))  
else:   
   print("Element is not present in list1")  

Output:

Element is present at index 2

Explanation

The above software is similar to the previous program. We declared a recursive characteristic and its base condition. The circumstance is the lowest fee is smaller or equal to the absolute best 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 remaining part, we have written our foremost program. It is the equal as the preceding program, but the solely difference is that we have exceeded two parameters in the binary_search() function.

This is due to the fact we cannot assign the preliminary values to the low, excessive and mid in the recursive function. Every time the recursive is called the price will be reset for those variables. That will provide the incorrect result.

Complexity

The complexity of the binary search algorithm is O(1) for the high-quality case. This show up if the factor that thing we are looking locate 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 performed to discover the thing that we are looking for.

Conclusion

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

We have discussed both techniques to locate the index position of the given number.