Implementing Binary Search in Python

Optimizing your code/ program is very important. Not only it helps in speeding up the task, but also it helps in reducing the memory required by the program. It helps significantly in allocating the resources, which are generally very limited. And to optimize our code, we must know how to use the most optimized algorithms for specific purposes. One such algorithm is the Binary Search Algorithm in python. As the name suggests, it is used for searching elements in an array.

When we want to search for the index of a particular element, if it is present, we generally use linear search or binary search. In Linear Search, we search for the element by iterating through the whole list or array. It takes a time complexity of 0(n). Suppose you have an array of 1 million numbers, iterating through 1 million numbers won’t be a choice right. That is where Binary Search comes into the picture, and it takes a time complexity of only O(log(n)). But there is a limitation with Binary Search. In this article, we will learn how to implement Binary Search in python, its advantages, and restraint. 

How do Binary Search works? 

In Binary Search Algorithm, we are given an element to search for and a sorted list, from which we have to find the index of the given element. What we do is we that find we find the middle element and compare our element with the middle element. If our element is higher than the middle element, we search for the element in the right part of the array and follow the same procedure. If our element is smaller than the middle element, we search for the element in the left part of the array and follow the same process of dividing and searching. We need to keep this in mind that binary search only works for already sorted lists.  

Algorithm of Binary Search 

Let us now see how binary search searches for an element in a sorted list using an example. 

Suppose the array (arr) is – [3,7,9,11,14,19,24,29,31] 

Element to be searched – 19 

Total elements – 9 (index – 0 to 8) 

Middle element= arr[4] = 14 

Steps- 

  1. Check if the element we are searching for is the middle element of the array. If it is true, then return the index of the middle element. Otherwise, go to step-2. 

Here, 19>14, so we will go to step 2

binary search python

2. If the element is higher than the middle element, search the element in 2nd half. Find the middle element of the second half and start the algorithm again. Otherwise, go to step-3. 

Here 19>14, so we will search in the second half. The middle element of the second half – 24.  

19 < 24, go to step-3. 

3. If the element is lesser than the middle element, search the element in 1st half. Find the middle element of the first half and start the algorithm again. 

Here as 19<24, we will search for the element in the new 1st half. Here the first half consists only of one element 19. Go to step –1 and check if the middle element is the element we are looking for. If yes, print the index of the element. Otherwise, print “Element Not Found.”

binary search python

Implementing Binary Search in Python. 

 In python, we can implement the Binary Search algorithm in two ways. First is by using recursion and second by using a loop. We will see both methods.  

a. Using Recursion

Here, we will keep calling the function using half part of the array until and unless we find the element’s index or we find that the element is not in the array.

# make a function that will return the index of the element we are #looking for.
def binary_search(arr,element,low,high):
    
    # If the lower index of the array exceeds the higher index,
    # that means that the element could not be found in the array.
    if low<=high:
        
        # find the middle index of the array 
        mid=(low+high)//2

        #If the middle element is the element we are looking for,
        # return the index of middle element
        if element==arr[mid]:
            print(mid)
        
        # if the element is greater than middle element,
        # search for the element in the second half
        elif element > arr[mid]:
            binary_search(arr,element,mid+1,high)
            
        # if the element is lesser than middle element,
        # search for the element in the first half
        else:
            binary_search(arr,element,low,mid-1) 
        
    else:
        print("Element not found")
arr=[3,7,9,11,14,19,24,29,39]

#At the start the low=0 as index of array starts from 0
low=0

#The last index will be the length of array-1
high=len(arr)-1

# Search for 29 in array
element=29
binary_search(arr,element,low,high)


# Search for 40 in array, which is not present
element=40
binary_search(arr,element,low,high)
7 
Element not found
# we can also use binary search algo on array full of characters
arr=['a','b','c','d','e','f','g']
element='f'
low=0
high=len(arr)-1
binary_search(arr,element,low,high)
5

b. Using while loop

Instead of using recursion, we can also use while loop.

def binary_search(arr,element):
    
    low = 0
    high = len(arr)-1
    
    # initialize the 'if_found' variable with False.
    if_found = False
    
    # run the loop until if_found becomes True and
    # lower index is greater and higher index.
    while( low<=high and not if_found):
        # find the index of middle element
        mid = (low + high)//2
        
        #If the middle element is the element we are looking for,
        # return the index of middle element  
        if arr[mid] == element :
            if_found = True
        
        else:
        # if the element is less than the middle element,
        # look for the element in the first part.
            if element < arr[mid]:
              # search for the element in array from index 0 to 
              # index mid-1
                high = mid - 1
            
            # if the element is greater than the middle 
            # element,look for the element in second part.
            else:
            # search for the element in array from index mid+1 to 
            # last index
                low = mid + 1
                
    # if the element is found, get out of the loop and print the 
    # index
   if if_found==True:
        return("Element {} found at index".format(element),mid)
    # if element is not in the array, run the below code
    else:
        return("Element {} Not found".format(element))
    
arr=[2,4,5,7,8,9,10]
element=7
print(binary_search(arr,element))
element=11
print(binary_search(arr,element))

Output:

('Element 7 found at index', 3) 
Element 11 Not found

Time and Space Complexity of Binary Search

Binary Search is a highly optimized searching Algorithm which takes O(1) time complexity for best case and 0(log(n)) for the worst case.

The best case will be when the element we are looking for is the middle element of the array. The worst case will be when the element is not in the array. For the average case also, the time complexity is 0(log(n)).

The disadvantage of Binary Search is that it only works for sorted lists and for lists whose elements contain a less than relationship.

Must Read:

Conclusion

Binary Search in Python is mostly used when we have sorted list and we can compare items if they are less than or greater than to each other. We have learnt both the ways in python – recursion and iteration. Recursion is less optimized and an iterative algorithm is more efficient because recursion takes space complexity of O(log(n)) while the iterative algorithm takes space complexity of O(1).

Try to run the programs on your side and let us know if you have any queries.

Happy Coding!

0 0 vote
Article Rating
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments
x