Binary Search

Implementation of binary search in python

Photo by Markus Winkler on Unsplash

Binary search can be implemented in two ways:-
1.Recursive ways
2.Iterative way

Here we are going to use the recursive method to implement binary search, What is recursion or recursive function?
In technical terms, recursive function are function which call itself. Using recursion certain problem like tower of Hanoi can be solved easily.

Advantages of using recursion:-
1. Code look simple and effective with use of recursive function.
2. We can split down a complicated function into a smaller problems utilizing recursion.
3. Sequence creation is simpler in recursion as compare to any nested iteration.

Disadvantages of using recursion:-
1. Debugging a recursive function is not easier.
2. A lot of memory and time is taken in recursive calls.

Now let discuss about binary search,

In below code snippet we are pass four values to the function binary_search()-
lst-It is a list in which we are looking for the value.
low-First index of the list.
high-last index of the list.
key-value to find in the list(lst).

First we will keep on iterating the list as long as the low becomes greater than high, then we will calculate the mid index of the list by adding low and high and then dividing it by 2.

def binary_search(lst, low, high, key):
    if low<=high :
        mid=(low + high)//2
        if lst[mid]==key:
            return mid
        elif lst[mid]>key:
            return binary_search(lst,low,mid-1,key)
        else:
            return binary_search(lst,mid+1,high,key)
    else:
        return None

The we will check in the elif-condition if the the key is less than the value at mid index if it is less than the mid-index value we can say that the key lies to the left-side of the mid-index, so we will update high to mid-1 and the new values will be :-
low=0
high=mid-1

If the key is greater than the mid-index value we can say that the key lies to the right-side of the mid, so we will update the low value to mid+1 and the new values will be :-
low=mid+1
high=len(lst)-1

we will pass this values to the function again as per the concept of recursion. Again the function will check if the key is present at mid or to left side of mid or right side of mid. It will keep on traversing the list in this fashion as long as low becomes greater than high.

If it is not found the else-condition is execute which will return a null value i.e key we are looking is not present in the list.

The complexity of the binary search algorithm is O(1) for the best case. This happen if the key we are looking found 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 key.

Conclusion-
Today we have learned how to implement Binary search in python…(cheers- PN)