The algorithm:

Binary search is a search algorithm that cuts down the time taken by linear search by a great amount.

In this algorithm, instead of comparing the values of each element, we compare the given value with the middle most element and recursively halve the sorted array.

We start with a sorted array. We then compare the element with the middle most element. If lower than the middle most element we restrict our field of search to only the first half. If greater, then we restrict our field of search to the greater half. We then repeat this till either the middle most element is the value we are searching for, the only element left is the value we are looking for or it is concluded that the element does not exist in the array.

Example:

Lets say that we have the following sorted array:

[ 2 , 3 , 6 , 8 , 10 , 12 , 15]

And say that we need to search for an element x = 6.

So first, we compare x with the middle most element of the array(8).

We find the 6<8, so we cut down the array and only look at the first half. The following is the new array:

[ 2 , 3 , 6]

We again look at the middle most element(3) and compare it with x.

On comparing it is found that 6>3 so we look only at the second half of the array. The following is the new array:

[6]

Since there is only one element left, the middle most term is the remaining element itself. On comparing, we find that x = 6 = 6. Hence we conclude that x is present in the given array. If the remaining list is null, i.e., it is empty, then it is safe to conclude that x is not in the given array.

The program:

Following is the implementation of binary search in python:

import math
 
def bs(v, l, g,  x):
   m = (l + g) // 2
   if l > len(v)-1:
       return -1
   if g >= 0:
       if x == v[m]:
           return m 
       elif x < v[m]:
           return bs(v,l,m-1,x)
       else :
           return bs(v,m+1,g,x)

print("Enter the array : ")
a = [int(i) for i in input().split()]
print("Enter the number : ")
x = int(input())
ans = bs(a,0,len(a)-1,x)
if ans == -1:
   print("It is not present")
else:
   print("It is present at index",ans)

The output of the program:

The github link for the program is:

https://github.com/HSNA243/PythonPrograms/blob/master/BinarySearch.py

Visits: 76

2 Replies to “Binary Search”

Leave a Reply

Your email address will not be published. Required fields are marked *