Program to search an element using Binary Search in Python

While performing linear search we need to go through each and every node thus it takes more time and hence increases the complexity.

In this python program we are going to use binary search which is an effective way to search an item from the list. In binary search our work become easy as the half of the array is ignored in first comparison. All we have to do is to take out the middle index and compare it with element we need to find.

The main point is that the binary search will perform on sorted array.

Algorithm:

1. The total number of items to enter in the array is asked from the user.
2. Array is created.
3. Input the number from the user which we need to search.
4. A function is created naming “binsearch()”
5. The function checks if the middle element is greater or smaller than the element that we need to find.
6. if middle<element then binsearch(A,m,b,q) is called.
7. if middle>element then binsearch(A,a,m,q) is called.
8. else if element==middle  
   print “element found”
   Else print” not found”
   Exit

Code:

def binsearch(A, a, b, q):
    m=int((a+b)/2)
    if (q> A[m]):
        binsearch(A, m, b, q)
    elif (q<A[m]):
        binsearch(A, a, m, q)
    elif (q== A[m]):
        print("the element is found on index:" )
        print(m+1)
    else:
        print("item not present in the list")
n=int(input("enter the total no. of elements: "r))
print("enter the elements:")
A=[]
for i in range(n):
    a=int(input())
    A.append(a)
print("enter the no. to be searched:")
q=int(input())
binsearch(A, 0, n-1, q)

Output:

enter the total no. of elements:  6
enter the elements:
1
2
3
4
5
6
enter the no. to be searched:  4
the element is found on index: 4