Python program to implement Binary Search


Binary Search :-

Binary Search is applied on the sorted array or list of large size. Binary search compares the target value to the middle element of the array. If they are not equal, the half in which the target cannot lie is eliminated and the search continues on the remaining half and again taking the middle element to compare to the target value, and repeating this until the target value is found. It’s time complexity of O(log n) makes it very fast as compared to other sorting algorithms. The only limitation is that the array or list of elements must be sorted for the binary search algorithm to work on it.

 


Python program to implement Binary Search


def binary_search(this_list, length, search_key):
    first = 0
    last = length-1
    while first <= last:
        middle = int((first + last)/2)
        if search_key == this_list[middle]:
            print("\n search number %d is present at position: %d" % (search_key, middle))
            return -1
        elif search_key < this_list[middle]:
            last = middle - 1
        elif search_key > this_list[middle]:
            first = middle + 1
    print("\n search Element not preasent in the list !!!")
    return -1
 
alist = []
 
lsize = int(input("Enter size of list: \t"))
 
for n in range(lsize):
    numbers = int(input("Enter the number number: \t"))
    alist.append(numbers)
 
alist.sort()
print('\n\n elements available in the  the sorted list is:', alist)
 
search_item = int(input("\nEnter the number you want to search: "))
 
binary_search(alist, lsize, search_item)

 

Output:-

Enter size of list:     5
Enter the number number:    11
Enter the number number:    9
Enter the number number:    45
Enter the number number:    22
Enter the number number:    13


 elements available in the  the sorted list is: [9, 11, 13, 22, 45]

Enter the number you want to search: 22

 search number 22 is present at position: 3
Enter size of list:     5
Enter the number number:    25
Enter the number number:    11
Enter the number number:    36
Enter the number number:    4
Enter the number number:    21


 elements available in the  the sorted list is: [4, 11, 21, 25, 36]

Enter the number you want to search: 101

 search Element not preasent in the list !!!

 

Leave a Reply

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