二进制搜索重复项，如果未找到目标 return 第一个较大元素的位置

Question

我想编写一个搜索算法，return确定目标值在排序数组中的位置。如果目标重复，return 第一个目标的位置。如果目标不在输入数组中，return数组中最近的较大元素的位置。

例如：

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

如果 target = 4 输出应该 return 4（元素 6 的位置），因为 4 不在数组中，而 6 是最近的较大数字。

if target = 3 输出应该是 2（数组中前 3 个的位置。

这是我最初的解决方案，但当目标不在数组中时它会失败

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

Answer 1

对于目标不在数组中的情况，循环的最后一步（其中 low == high）可以收敛于小于目标的值（在 2 in [2,4] 当目标为 3 时），或直接较大的值（在上一个示例中为 4）。

您可以使用临时变量来跟踪 mid 的最后一个值，其中 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

如果目标大于数组中的所有元素，这将 return None。

二进制搜索重复项，如果未找到目标 return 第一个较大元素的位置

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

python

arrays

algorithm

search