Get the index of the last occurrence of the element that is strictly greater than or equal to a target value(in a sorted array)

Given that we have a sorted array and a target value, I wish to find the index of the last occurrence of the element that is strictly greater than or equal to the target value. This implies that there may be several duplicates of this value in the sorted array.

Sample input and expected output:

array = [1,1,1,1,2,2,2,2]  target = 1  >>find_next(array, target)  #should return 7      array = [7,7,7,7,9,9,9,9,11,11,11]  target = 8  >>find_next(array,target)  #shoud return 7        array = [7,7,7,7,9,9,9,9,11,11,11]  target = 2  >>find_next(array,target)  #shoud return 0    array = [7,7,7,7,9,9,9,9,11,11,11]  target = 9  >>find_next(array,target)  #should return 7    array = [1,1,3,4,5,7,10,10,11]  target = 5  >>find_next(array,target)  #should return 4      array = [1,4,7,13,14,14,14,15,15]  target = 13  >>find_next(array,target)  #should return 6  

This is my failed attempt so far:

def find_next(array,target):     if target < min(array):         return 0     n = len(array)     lo = 0     hi = n-1     succ = None     mid = (lo + hi) // 2     diff = array[mid] - target         while (lo < hi):         mid = (lo + hi) // 2         if diff < 0:             lo = mid + 1         elif  diff > 0:             if (mid-1 > 0) and array[mid - 1] - target < diff:                 succ = array[mid -1]                 hi = mid - 1                 diff = array[mid - 1] - target             elif (mid + 1) < len(array) and array[mid + 1] - target == diff:                 lo = mid+1                 succ = mid+1                 diff = array[mid + 1] - target             else:                 break         else:             if (mid + 1) < len(array) and array[mid + 1] - target == diff:                lo = mid+1                succ = mid+1                diff = array[mid + 1] - target             else:                break     return succ  

Apologies if the indentation is out of order. Any help would be highly appreciated!

https://stackoverflow.com/questions/66816979/get-the-index-of-the-last-occurrence-of-the-element-that-is-strictly-greater-tha March 26, 2021 at 08:28PM