Consider the binary search algorithm from def binarySearch(values, low, high, ta
ID: 3768720 • Letter: C
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));