二分查找实现条件混淆

Question

我是用二分查找来解决问题的，当我看到有些地方有人使用while start < end时我感到困惑，但在算法中我的理解是它应该是while start <= end。

例如，这里是 Leetcode 问题的解决方案找到大于目标的最小字母：

def nextGreatestLetter (self, letters: List[str], target: str) -> str:
    l, r = 0, len(letters)-1

    # cross the border
    if target >= letters[-1]:
        return letters[0]

    while l < r:
        mid = (l+r)//2
        if letters[mid] <= target:
            l = mid+1
        else:
            r = mid
    return letters[l]

为什么我们没有递减 r = mid - 1 并且为什么没有 while l <= r？我真的很困惑。

Answer 1

这些是实施细节。有多种实现一切的方法。

在这种情况下，循环条件是 l < r（不是 l <= r），因为当 l == r（即搜索中只有一个元素 space）时，我们不必进一步处理，预期结果（ceil）是位置 l.

处的元素

并且更新语句是 r = mid（不是 r = mid - 1），因为更新发生在 target < letters[mid] 时，我们不能根据这个条件丢弃中间的元素。例如，假设 (mid - 1) 处的元素可能小于或等于目标，在这种情况下，我们的结果将是 mid[=33= 处的元素].

就像我说的，这些只是实现细节，同样的解决方案也可以这样实现：

def nextGreatestLetter (self, letters: List[str], target: str) -> str: l, r = 0, len(letters)-1 # cross the border if target >= letters[-1]: return letters[0] while l <= r: mid = (l+r)//2 if letters[mid] <= target: l = mid+1 else: r = mid - 1 return letters[l]

我们在循环内处理 l == r 案例的实现也是正确的，并且通过了 Leetcode 上的所有测试用例。

PS: 我假设您最近开始了竞争性编码，所以这只是给您的建议。不要试图记住实现并专注于算法的关键，同样因为有多种实现相同算法的方法。

二分查找实现条件混淆

Binary search implementation conditional confusion

binary-search