Skip to main content

Binary Search Using Functions in Python




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

Popular posts from this blog

Palindrome Checker Using Python

  Problem:               To find whether a given input is a palindrome or not. We use two methods to find the palindrome, one is using "reverse indexing" and "reverse function". Palindrome:  The term palindrome means, consider a string and reverse it then compare both the                                 string if they are equal then it is a palindrome. Code: def palindrome ( a ):     if a == a [::- 1 ]:         print ( "It is a Palindrome" )     else :         print ( "It is not a Palindrome" ) val = input ( "Enter the value" ) palindrome ( val )