Do as basic Binary Search algorithm in Python 3 for a sorted sequence of numbers
ID: 3700929 • Letter: D
Question
Do as basic Binary Search algorithm in Python 3 for a sorted sequence of numbers.
For lists of even size, the middle index is the previous of the two middle elements. For example, if the given list is
[0, 1, 2, 3], then the middle element would be 1 and not 2.
Where binary_search(list,item)
returns the index of the target value item if it is found in the given list.
return the index the value would be at if it were inserted in order, if item is not found in the given list. <------- more important
>>>list = [1, 4, 5, 8, 11, 15]
>>>binary_search(list,5)
2 <---found
>>>binary_search(list,9)
4
>>>binary_search(list,0)
-1
Explanation / Answer
'''
WRITTEN IN PYTHON 2.7
'''
def binary_search(list,item):
front = 0 #front = 0
len1 = len(list) #len1 = length of list
end = len1-1 #end of list
pos = -1 #position of given item to search
if(len1%2 == 0):
middle = (front+end)//2-1
else:
middle = (front+end)//2
while(front<=end):
#middle element is less than item move front to middle
if(list[middle]<item):
front = middle+1
#if(middle position) element = given item then return position
elif(list[middle] == item):
pos = middle
break
#if middle element is greater than item then move end to middle -1
else:
end = middle -1
middle = (front+end)//2 #middle is division of (front+end) with 2
return pos
print("Enter List(input should be in sorted order) : ")
list1 = list(map(int,input().strip().split(' ')))
print ("Enter item to search : ")
item = int(input(''))
pos = binary_search(list1,item)
if(pos==-1):
print (pos)
else:
print (pos,"<----found")
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.