排序数组中元素的上限

Question

嗨，我正在做 DSA 问题，发现一个称为排序数组中元素上限的问题。在这个问题中，有一个排序数组，如果目标元素存在于排序数组中，则返回目标。如果在排序数组中找不到目标元素，我们需要返回大于目标的最小元素。我已经编写了代码并完成了一些测试用例，但需要检查一切是否正常工作。这个问题在 leetcode 上不存在，我可以在许多不同的情况下运行它。如果问题以正确的方式解决并且在所有情况下都能给出正确的结果，则需要建议/反馈

class Solution:
    #My approch
    def smallestNumberGreaterThanTarget(self, nums, target):
        start = 0
        end = len(nums)-1

        if target > nums[end]:
            return -1
        while start <= end:
            mid = start + (end-start)//2

            if nums[mid] == target:
                return nums[mid]
            elif nums[mid] < target:
                if nums[mid+1] >= target:
                    return nums[mid+1]
                start = mid + 1
            else:
                end = mid-1

        return nums[start]

Answer 1

IMO，这个问题可以用一种更简单的方式解决，只需在主循环内进行一次测试。下图显示了实线的分区，在与数组中的值关联的子集中。

首先，我们注意到对于大于最大值的所有值，没有对应的元素，我们将单独处理这种情况。

现在我们正好剩下 N 个子集，我们可以通过在这些子集中进行二分搜索来找到正确的子集。

if target > nums[len(nums)-1]:
    return None

s, e= 0, len(nums);
while e > s:
    m= e + ((s - e) >> 1);
    if target > nums[m]:
        s= m+1
    else:
        e= m
return s

我们可以使用不变式

nums[s-1] < target <= nums[e]

和虚构约定

nums[-1] = -∞

来正式证明该算法。最后，我们得到了包围

nums[s-1] < target <= nums[s]

。

Answer 2

代码因空列表的索引超出范围错误而出错（尽管这可能不是必需的，因为您尚未指定问题约束）。

函数顶部的一个简单的

if

防护可以解决这个问题：

if not nums:
    return -1

否则，我觉得还好。但是，如果您仍然不确定您的算法是否有效，您可以随时进行随机测试（例如，创建算法的线性搜索版本，然后随机生成两种算法的输入，然后查看是否有任何差异）。

这是您可以测试的单行代码：

input_list = [0, 1, 2, 3, 4]
target = 0
print(next((num for num in input_list if num >= target), -1))

Answer 3

您也可以在这里使用

bisect

-

import bisect
bisect_left(nums, target)