Binary Search Algorithm in Python (Explained)

Binary Search in Python Explained

Binary search also known as half-interval search, logarithmic search is an algorithm used in computers to find the position of a value in a sorted array.

Bubble sort, Linear search, Quick sort are some of the other type of sorting algorithm available. In this article we are going to learn about the searching algorithm known as Binary search.

Binary search is little bit more advanced and have more accurate results when compared with linear search and bubble sort algorithms.

So let’s assume that you have a list with 10000 items in it. The item you are looking for is in the 9000th place. If you implement the linear search algorithm in this scenario it will take much time to give you the result. Because the algorithm needs check each and every item in the list.

So how can we write our code to show the result quickly? Here’s how….

We have a list with the following items.

The List

So first we need to specify the Lower bound (L) and Upper bound (U). Lower bound is the first index of the list and upper bound is the last index of the list.

specifying the lower bound and upper bound

Once you finish assigning these bounds you have to find a mix index (M).

So what is mid index? As name implies it is the middle position between lower and upper bounds. So we can say that,

Mid Index = (Lower bound + Upper bound)/2

In my case, Mid Index = (0 + 13)/2 = 6

Mid Index

In here we are doing integer division not float division. Therefore 13/2 = 6 not 6.5.

Now let’s specify the item that we need to find from our list. Let’s say we need to find number “90” from our list.

OK now the mid value we got is 6. The value of index 6 in our list is 10.

Now we have to check whether if mid value is matching the item that we are searching. (10 ≠90) Since they are not matching we need to change the lower bound or the upper bound. How do we know which one to change? Here’s how…

You have to check the value you are searching for is smaller or bigger than the mid value. If the value is smaller change upper bound and mid value becomes the new upper bound. If value is greater change lower bound and mid value becomes new lower bound.

So in my case the search value is bigger there for I need to change my lower bound and the mid value (10) becomes my new lower bound.

Now we got a new lower bound (10) and the upper bound (1000) values. Now we can again find a mid-value.

New upper bound and lower bound

Mid Index = (Lower bound + Upper bound)/2 = (6 + 13)/2 = 9

Now once again we can check if mid value is matching the item that we are searching. So according to my case they are matching. Which means we found our item from the list.

That’s how you do the binary search. If you have huge list this method will be a lifesaver. There is one main drawback in this search method. You need to have a sorted list if you want search your list using binary search.

Since we have talked all about the logic behind binary search now let’s implement this logic into python code.

def search(list, n):

    l = 0
    u = len(list)-1

    while 1 <= u:
        mid = (l+u) // 2
        
        if list[mid] == n:
            return True
        else:
            if list[mid] < n:
                l = mid+1
            else:
                u = mid-1
    return False

list = [1,3,4,7,8,9,10,45,50,90,100,150,600,1000]
n = 90

if search(list, n ):
    print("Found")
else:
    print("Not Found")