Movatterモバイル変換

Python program to implement Binary Search Algorithm

AVINASH NETHALA2 years ago2 years ago05 mins

Hello everyone! Welcome back toprogramminginpython.com. Here in this post am going to show you how to implement a binary search algorithm in Python. In theprevious post, I discussedthe Linear Search Algorithm which is a very basic search algorithm here I will discuss Binary Search.

Binary Search as the name suggests binary, here the list is divided into halves and then searched in each half. One notable thing about this binary search is that the list should be sorted first before executing the algorithm. The list is divided into two halves by the index, find the mid element of the list and then start to mid-1 is one list and mid+1 to end is another list, check if the element is mid, greater than it, or less than it and return the appropriate position of the key element to be found.

Master the basics of data analysis in Python. Expand your skillset by learning scientific computing with numpy.
Take the course on Introduction to Python onDataCamp herehttps://bit.ly/datacamp-intro-to-python

https://www.youtube.com/watch?v=TpPi5TCSE5Q”]

You can also watch the video on YouTubehere

Program on GitHub

Ad:
Learn Python Programming Masterclass –Enroll Now.
Udemy

Binary Search Algorithm – Code Visualization

Time Complexity

Best Case	O(1)
Average Case	O(log n)
Worst Case	O(log n)

Program on GitHub

Algorithm

Given a list L of n elements with values or records L0, L1, …, Ln-1, sorted in ascending order, and given key/target value K, binary search is used to find the index of K in L

Set a variablestart to0 and another variableend ton-1(size of the list)
ifstart >end break the algorithm, as it works only on sorted lists
calculatemid as(start + end)/2
if the key element is
1. equal to mid, the search is done, returns the position of mid
2. greater than mid, setstart tomid + 1 and repeat step 2
3. less than mid, setend tomid - 1 and repeat step 2

Program

__author__ = 'Avinash'def binary_sort(sorted_list, length, key):    start = 0    end = length-1    while start <= end:        mid = int((start + end)/2)        if key == sorted_list[mid]:            print("\nEntered number %d is present at position: %d" % (key, mid))            return -1        elif key < sorted_list[mid]:            end = mid - 1        elif key > sorted_list[mid]:            start = mid + 1    print("\nElement not found!")    return -1lst = []size = int(input("Enter size of list: \t"))for n in range(size):    numbers = int(input("Enter any number: \t"))    lst.append(numbers)lst.sort()print('\n\nThe list will be sorted, the sorted list is:', lst)x = int(input("\nEnter the number to search: "))binary_sort(lst, size, x)

Program on GitHub