这里是二分查找的代码,不知道是不是没有匹配值,问题是上界应该定位在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
最佳答案
@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
。
关于python - 使用二进制搜索找到上限和下限值,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/33002335/