Binary Search
Basic idea behind binary search is to divide sorted array in two parts, and check whether the element which divides the array is desired element . And if the desired element is found then stop the search, otherwise further
divide the array until the desired element is not found.
Step-Wise Pictorial Demonstration of Search Procedure
Binary Search in Python
To demonstrate binary search in Python. I have taken a list of integers a of having 10 elements. We have set item 18 to be searched.
Furthermore, see the program and you can easily understand if you have understood pictorial demonstration of search procedure.
import math
a=[5,6,9,12,17,18,20,25,30,35]
index=0
start=0
end=len(a)
item=18
mid=-1
while start <= end and item != a[mid]:
mid =math.floor((start+end)/2)
print(‘mid’,mid)
if item == a[mid]:
print(‘Position of the given element is’,mid+1)
print(‘Element is’,a[mid])
else:
if item < a[mid]:
end=mid-1
else:
start=mid+1
Time Complexity of Binary Search Algorithm
Time complexity of binary search algorithm is O(log2n). However, it requires a sorted array to perform search operation.