Consider the binary search algorithm from Section 12.6.2. If no match is found,
ID: 3838001 • Letter: C
Question
Consider the binary search algorithm from Section 12.6.2. If no match is found, the binarySearch function returns -1. Modify the function so that if target is not found, the function returns –k, where k is the position before which the element should be inserted. The output of your program should say: 5 pts Found in position xx Or Not Found. Insert before value zz
12.6.2 - ## Finds a value in a range of a sorted list, using the binary search algorithm.
# @param values the list in which to search
# @param low the low index of the range
# @param high the high index of the range
# @param target the value to find
# @return the index at which the target occurs, or -1 if it does not occur in the list
#
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
Explanation / Answer
In binary search the last mid value which we will compare is the index value which the element can be inserted before so the element must be compared with the mid to know to place it left of mid or right of mid ,the modified algorithm will be like this
def ModifiedbinarySearch(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 - (values[(low+high+1)/2]> target ? (low+high+2)/2 : (low+high)/2 )
//here the mid value can be obtained by mid = low+high+1 and compared to target to know the location