排序数组中元素的上限

Question

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

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

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

函数顶部的一个简单 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 2

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].

排序数组中元素的上限

Ceiling of the element in sorted array

python

algorithm

binary-search

data-structures