Binary Search program in python

1. QUESTION:

Binary Search Program Using Python Programming

LOGIC:

• We pass the list, the length of the list and the number to search to a function b_s(binary_search)
• The start and end position is initially 0 and n-1, where n is the length of the list.
  we calculate middle position using mid = (first+ last)/2 
• If the number to be searched is equal to the number at the middle position then it is simply returned
  but if its less than the middle number then change last to mid -1 and if its greater than the middle element then first is changed to mid + 1
  
• In the next iteration of the while loop, the number is again matched with the new middle element and so on.
• The while loop is terminated if start becomes greater or equal to end, that simply means that there is nothing left to search. after the while loop terminates on meeting this condition  -1 value is returned to denote that the element was not found.

PROGRAM: 

Number = input('Enter the sorted list of numbers: ') #Get the input from the user
Number = Number.split()								 #split the input
Number = [int(a) for a in Number]					 
r = int(input('Number to search for: '))			 #Search the number 
def b_s(Num, r):									 #Function Declaration for binary search
    first = 0
    last = len(Num)									 
    while first < last:								 #The last variable value is greater than first variable value
        mid = (first + last)//2						 #add the first and last variable value and divide by 2, that is to find the mid element value
        if Number[mid] > r:
            last = mid
        elif Number[mid] < r:
            first = mid + 1
        else:
            return mid
    return -1
 
s = b_s(Number, r)									 #store the value to s variable
if s < 0:
    print("{} was not found".format(r))				  #The element is not found
else:
    print("{} was found at index {}".format(r, s))	  #The element is found
</pre>