Python

Python Binary Search

This article will show you how to use Python to perform a binary search technique to locate an entity’s index position in a list.

A binary search is a way of finding a certain element within a list. Let’s imagine we have a ten-thousand-element list and need to find the index position of a single entry. We can quickly find the index location of an element using the binary search technique. Other search algorithms exist, but the most extensively employed is a binary search. Sort the objects first if they haven’t already been sorted.

The binary search algorithm’s recursive and iterative approaches can be utilized to find the element position. The recursive strategy is used after the divide and conquer approach. In this manner, a function is performed until it finds an element in the list. To discover an element’s index location, the iterative technique repeatedly repeats a set of words. This process is accomplished using the while loop. Because we don’t have to search each list index, binary search is more efficient than linear search.

Let’s start with a basic understanding of binary search.

Example 1:

First, we use the iterative approach to implement a binary search. We’ll cycle through the list, repeating a sequence of statements. We’ll continue searching for the center value until we find it.

This is a Python implementation of the iterative binary search function approach. If ‘search_num’ is present in the given list, it returns one; otherwise, it gives -1. We constructed the binary search() function in this program, which accepts two arguments: a list to sort and a number to search. We’ve set up two variables to keep track of the list’s lowest and greatest values. The low has a starting value of 0, the high has a value of len(list1) – 1, and the middle has a value of 0. The while loop is then written with the constraint that the lowest equals and is smaller than the highest. The while loop will iterate if the number hasn’t been found yet. The midpoint is found in the while loop. Then we match the index value to the number we’ve been looking for. If the mid-index value is less than ‘search num,’ we assign it to and raise the mid-index value by one. The focus of the search changes to the left. Set the mid value to the maximum if it is high. Return mid if the ‘search_num’ is equal to the mid value. This will continue until the low and high are equal and the low is smaller than the high. If we get to the end of the function, we know that the element isn’t in the list. To the invoking function, we return -1.

def binary_search(one, search_num):  
    low = 0  
    high = len(one) - 1  
    mid = 0  
    while low <= high:  
        mid = (high + low) // 2  
        if one[mid] search_num:  
            high = mid - 1  
        else:  
            return mid  
    return -1  
one = [19, 23, 43, 56, 65, 71, 80]  
search_num = 43
output = binary_search(one, search_num)  
if output != -1:  
print("Element is at index", str(output))  
else:  
print("Element is not available in the list")

Here you can see that the required number is found at index position 2.

Example 2:

Let’s look at the recursive binary search approach. The recursion approach can be used in binary search. We’ll make a recursive function that calls itself until the condition is satisfied. The preceding program is similar to the one before it. A recursive function, as well as its base condition, were declared. We compute the middle number as we did in the previous program. To continue with the binary search, we used the if statement. It’ll be returned if the mid value is equivalent to the number we’re looking for. If the mid value is below the value, we increase it by one and assign it to low using our recursive binary search() function. We wrote our main program in the last section. The binary search() procedure now requires 2 parameters, which is the only modification from the prior program. The inability of the recursive function to assign starting values to the low, high, and mid is the reason behind this. The value for those variables will be reset every time the recursion is called.

def binary_search(one, low, high, search_num):  
   if low search_num:  
         return binary_search(one, low, mid - 1, search_num)  
      else:  
         return binary_search(one, mid + 1, high, search_num)  
   else:  
      return -1  
one = [19, 23, 43, 56, 65, 71, 80]  
search_num = 65
output = binary_search(one, 0, len(one)-1, search_num)  
if search_num != -1:  
print("Element is at index", str(output))  
else:  
print("Element is not available in the list")

The required value is at index 4, as you can see in the following image.

Example 3:

Another example of a binary search technique, commonly known as a half-interval search algorithm, is used to locate a target value within a sorted array. This program returns true if the number is located in the list.

def binary_search(my_list,search_num):
    one = 0
    final = len(my_list)-1
    found = False
    while( one<=final and not found):
        mid = (one + final)//2
        if my_list[mid] == search_num :
            found = True
        else:
            if search_num<my_list[mid]:
                final = mid - 1
            else:
                one = mid + 1  
    return found
   
print(binary_search([1,2,3,4,5], 3))
print(binary_search([11,22,33,44,55], 5))

Below is the output.

Conclusion:

The most effective and quick approach to search for an entry in a list is to use a binary search algorithm. It skips over the meaningless analogy. As the name says, the search is divided into two pieces. It concentrates on the side of the list closest to the number we are looking for. In the best situation, the binary search algorithm’s complexity is O(1). This occurs when the element we’re seeking appears in the first comparison. The worst and average case complexity of the binary search is O(logn). The total number of searches required to locate the item determines this. Different approaches for determining the index position of a given number have been discussed.

About the author

Kalsoom Bibi

Hello, I am a freelance writer and usually write for Linux and other technology related content