What is Binary Search and How to implement in Python
In this tutorial, we will learn about the standard Binary search algorithm and will implement it in Python.
Binary Search in Python
This searching technique reduces the number of comparisons and hence save on processing time. It compares the element to be found with the middle element and then goes on further eliminating one half of the array; finally leading to the desired element at the middle position.
TIME COMPLEXITY of Binary Search:
Binary search in the worst case scenario would make log(n) comparisons; making the time required to be O(logn), where n is the number of elements in the array.
SPACE COMPLEXITY of Binary SEarch:
Binary Search takes constant space irrespective of the number of elements in the array taking the space required to be of the range O(1).
DISADVANTAGE of Binary Search:
The only downside of this algorithm is that it cannot work with unsorted arrays – the array should be sorted either in ascending or descending order.
Implementing Binary Search in Python
data_list=list(map(int , input().split())) value=int(input()) low=0 high=len(data_list) while(low<high): mid=int((low+high)/2) if(data_list[mid]==value): print("Element found at ",mid) break elif(data_list[mid]<value): low=mid+1 elif(data_list[mid]>value): high=mid-1 if(low>=high): print("Element not found")
12 25 43 59 61 78 92 25
Element found at 1
Let us consider that the element, value has to be searched in a list that is sorted in ascending order. value if first compared with the middle element; if value is greater than the middle element, the second half of the list becomes new segment to be searched. If the value is less than the middle element, the first half of the list is scanned for the value.
The process is repeated till either the element is found or we are left with just one element in the list to be checked and the value is still not found.
That’s it! Hope you have understood the concept of Binary Search.
Feel free to ask any doubts regarding the algorithm in the comments section below.
Also, have a look at other posts too,