Summery: In this article you will learn Binary Search in Python
So in the last article we’ve talked about the linear search in python. If you miss that post you can check it out from here. In this article we are going to learn about another searching method known as Binary Search.
Binary search is little bit more advanced and have more accurate results when compared with linear search. So let’s assume that you have a list with 10000 items and the item you are looking for is in the 9000th place in the list. If you implement the linear search 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.
Also Read: Python Encryption and Decryption
So how can we write our code to show the result quickly? Here’s how….
We have a list with the following items.
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. 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
In here we are doing integer division not float division. Therefore 13/2 = 6 not 6.5. Not let’s specify the item that we need to find from our list. 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.
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 this search now let’s implement this logic into codes….
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")