python - 使用二进制搜索找到上限和下限值

Question

这里是二分查找的代码，不知道是不是没有匹配值，问题是上界应该定位在small还是small+1？下界应该位于 small 或 small-1，对吗？谢谢。

def binary_search(my_list, key):
    assert my_list == sorted(my_list)

    large = len(my_list) -1
    small = 0

    while (small <= large):
        mid = (small + large) // 2 )
        # print small, mid, large, " - ", my_list[mid], "~", key
        if my_list[mid] < key:
            small = mid + 1
        elif my_list[mid] > key:
            large = mid - 1
        else:
            return mid

    raise ValueError

Answer 1

@Paul 很接近，它应该返回 mid+1 作为上限值。这里没有引发异常，而是返回上下限值的 Python 代码:

value = my_list[mid]
lower = mid if value < key else mid-1
upper = mid if value > key else mid+1
return (lower, upper)

这里有一个更简单的答案:

return (small-1, small)

因为 small 在您查找时位于 key 的索引之上，所以下限是 small-1 并且上限是 small。