Consider the binary search algorithm from def binarySearch(values, low, high, ta

Question

Consider the binary search algorithm from

def binarySearch(values, low, high, target) :

if low <= high :

mid = (low + high) // 2

if values[mid] == target :

return mid

elif values[mid] < target :

return binarySearch(values, mid + 1, high, target)

else :

return binarySearch(values, low, mid - 1, target)

else :

return -1

If no match is found, the binarySearch function returns -1. Modify the function so that if target is not found, the function returns –k -1, where k is the position before which the element should be inserted.

Explanation / Answer

Here is the solution for you. If you need any refinements, just get back to me.

#! /usr/bin/python

def binarySearch(values, low, high, target) :
if low <= high :
mid = (low + high) / 2
if values[mid] == target :
return mid
elif values[mid] < target :
return binarySearch(values, mid + 1, high, target)
else :
return binarySearch(values, low, mid - 1, target)
else:
if(values[(low+high)/2] > target):
return low-1;
else:
return low;

print(binarySearch([10,20,30,40,50], 0, 4, 15));   

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.