Binary Search with duplicates, if target is not found return the position the first larger element-CodePudding

I want to write a search algorithm that returns the position of the target value on a sorted array. If the target is duplicated, return the position of the first target. If the target is not in the input array, return the position of the nearest larger element in the array.

for instance:

A = [1,2,3,3,6,7,8]

if target = 4 the output should return 4 (position of element 6) as 4 is not in the array and 6 is the nearest larger number.

if target = 3 the output should be 2 (position of the first 3 in the array.

This is my initial solution but it fails in the case when target is not in the array

def BinSearch(A, target):
    low = 0
    high = len(A)-1
    
    while low <= high:
        mid = (low   high)//2
        
        if A[mid] < target:
            low = mid  1
        elif A[mid] > target:
            high = mid -1
        else:
            if mid - 1 < 0:
                return mid
            if A[mid-1] != target:
                return mid
            high = mid - 1


A = [1,2,3,3,6,7,8]
target = 4
BinSearch(A, target) 
#It returns none, but I expect 4 as output

CodePudding user response：

For cases where the target isn't in the array, the last step of the loop (where low == high) could converge at the value either smaller than the target (at 2 in [2,4] when target is 3), or at the immediately larger value (at 4 in the previous example).

You could use a temp variable to track the last value of mid where A[mid] > target.

def BinSearch(A, target):
    low = 0
    high = len(A)-1
    ans = None
    
    while low <= high:
        mid = (low   high)//2
        
        if A[mid] < target:
            low = mid  1
        elif A[mid] > target:
            high = mid -1
            ans = mid # since mid is outside the outer limit of the new search space
        else:
            if mid - 1 < 0:
                return mid
            if A[mid-1] != target:
                return mid
            high = mid - 1
    return ans

A = [1,2,3,3,6,7,8]
print(BinSearch(A, 3)) # 2
print(BinSearch(A, 4)) # 4

This will return None if the target is greater than all elements in the array.