重复的二进制搜索，如果没有找到目标，则返回第一个较大元素的位置

Question

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

例如：

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

如果target = 4输出应该返回4(元素6的位置(，因为4不在数组中。

如果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(可以收敛于小于目标的值(当目标为3时，在[2,4]中的2(，或者收敛于紧接着更大的值(在上一个示例中为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

如果目标大于数组中的所有元素，则返回None。