Binary Search in Python

This guide will teach how to implement a binary search algorithm in Python while looking for a particular number in a list.

What is Binary search in Python

A Binary Search in Python is a technique for finding a specific element in a sorted list. The algorithm operates by recursively splitting sublists until they can be searched to the desired value. When scanning massive arrays, a binary search is much more effective than a linear search. Specifically, the binary search runs at a logarithmic time in the worst case, O(log n), while linear search runs at linear time O(n) in the worst case. We will concentrate on how to write a binary search algorithm in Python.

Concept of binary search in Python

Before continuing the search, you have to understand the binary search. All the values have to be sorted. Normally, when you work with linear search, it’s not composite to have the values sorted. We can have values in any order, but you have to make sure that your values are sorted in the case of binary search. That means if I provide initial values example to be operating values like this

[45, 8, 4, 7, 12, 99]

so we will change it we will have a value which is sorted. so let’s

[4,7,8,12,45,99]

So we have six values. I want to search for a particular value now how that works, so what you will do is you will first specify the lower bound and the upper bound so as you can see, the first value is a lower bound, and the last value is the upper bound. you have to find a midpoint of this lower and upper so that you would say

Mid index = (lower + upper)/2
= (0 + 5)/2
= 2

You will get mid-value now, so in this case, you can see we caught the mid-value 2, and the element is 8.

If you want to search 45, so you can see if we got the mid-body, so what’s up to mid-value so the index value for 4 is 0 the next value for 99 is 5. so if it’s lower plus 5 is 5 and 5 divided by 2 is 2, so we are doing integer division area. We are not doing flow division, so we are doing into the division to give you 2, so the value at index value is your mid, 2. Hence, the value at that index is 8, so now we got 8 as the mid-value.

The next step is to match the element searching for. The element we are searching for is 45. so it’s not matching now. The next step would be to change your lower bound or upper bound for the next iteration.

You’re searching for is smaller or bigger than the mid-value. If the value is smaller, change your upper bound. That means you will say the mid-value is the new upper bound.

If your value is greater than the mid-value, the mid-value here is 8, and the values you are searching for are 45, so now you have to change your lower bound. So what you will do is so the lower bound now it will to the mid-value, so Upper of Mid-value becomes Lower. So instead of having a big reach time, you’ve got a small list, so it starts at 8, and it ends at 99. Now you’ve got a new lower and the upper value.

so what you will do you will again find a mid value so that’s what you do every time so your lower plus upper so what is your lower is basically 2 and your and your upper is 5, so mid-value is

Mid index = (lower + upper)/2
= (2 + 5)/2
= 3

So now 12 becomes your new mid-value. Is it matching? I get the same thing. It’s not matching. We are searching for 45. You have to change your lower value because 45 is bigger than 12, so you will shift your lower value to 12 now. Hence, 12 is the lower value, and 99 is the upper value so what you will do now is you will say meet the lower value again is 3 the upper value is 5 submit becomes 4, and at 4 we have 45 so now you will check, and you’ve got the value now you might be thinking.

let’s implement this with a code now, so what you’re going to do is let’s keep the same code

Python Program for Binary Search

pos = -1
def search(list,n):
    l = 0
    u = len(list)-1
    while l<=u:
       mid = (l+u) //2
       if list[mid] == n:
          globals()['pos'] = mid
          return True
       else:
           if list[mid] < n:
              l = mid;
           else:
              u = mid;
list = [4,7,8,12,45,99]
n = 45
if search(list,n):
   print("Found at ",pos+1)
else:
   print("Not Found")

Output: