#sorted = [2,4,5,8,9,12,18,22,25,30,40]
sorted = [2,4,4,4,4,4,9,9,12,18,22,22,22,22,25,30,40]
def binary_search(value,sorted):
        left = 0
        right = len(sorted)-1
        while left <= right:
            mid = int((left+right)/2) # get the index of mid value in the list
            print ('mid is ', mid)
            if sorted[mid]> value:
                right = mid -1
            elif sorted[mid]< value:
                left = mid+1
            else: # return the position of the first instance of the value
                pos = mid
                while sorted[pos-1]== value:
                    pos= pos -1
                return pos
       # from heir is the code to return closest value in the absence of any match
        lower = value - sorted[mid-1]# find difference with value at lower index
        upper = sorted[mid +1]-value # find difference with value at upper index
        middiff= abs(value-sorted[mid])# find difference with value at mid index
        while mid != len(sorted)-1:# runs as long as the mid value is not the last value in the list
            if middiff < upper and middiff< lower:
                return mid
            elif lower< upper:
                return mid-1
            elif lower> upper :
                return mid +1
            else:# if lower and upper are equal, return value at lower index
                return mid-1
        if middiff < lower: # if the value is the last value in the list, we calculate only difference with value at  lower index
            return mid
        else:
            return mid-1#if equal return value at lower index

print(sorted)
x = binary_search(27.5,sorted)
print(x)
print(sorted[x])