Problem:
To find an element from a python list using "Binary Search" method. This search is quite different from Linear Search. There we used a loop to traverse and searched for element but here we first sort the list and compare the key value to the mid value of the list if it matches, we found the element or else we split the list into two one half consists of the elements lesser than the mid value and other half consists of the elements greater than the mid value, This process is repeated till we find a match.
Code:
def binarysearch(a,k,start,end):
mid=int((start+end+0.1)/2)
if a[mid]==k:
print("number found at position ",mid+1)
elif a[mid] > k:
binarysearch(a,k,start,mid)
elif a[mid] < k:
binarysearch(a,k,mid,end)
list1=list(map(int,input("Enter list elements:").split(',')))
list1= list1.sort()
key=int(input("Enter the value to search:"))
binarysearch(list1,key,0,len(list1))
- Here we got input from the user using the "Map function" and sorted it and took the key input. Then we pass the list, key, starting value, ending value to the function.
- In that function we check the middle value is equal to the key or we use recursion function to split the list.
Bonus Code 😍 :
def binary():
r='false'
a.sort()
if val <= (len(a)//2):
for i in range(0, ((len(a)//2)+1)):
if str(a[i]) == str(val):
r='true'
elif val >= (len(a)//2):
for j in range(((len(a)//2)-1),len(a)):
if str(a[j]) == str(val):
r='true'
if r == 'true':
print(val,' is found in the list')
elif r=='false':
print(val,' is not found in the list')
l=input("Enter the list values:")
val=int(input("Enter the value to search:"))
a=l.split(',')
binary()
[Note : The above code is without functions and recursion method]
Comments
Post a Comment