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

这里是二进制搜索的代码，想知道如果没有匹配值，问题是上限应该定位在小或小的+1？下界应该位于小或小-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

来源

2015-10-07 Lin Ma

嗯......问题是什么？ – Paul

@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。

来源

2015-10-07 23:23:12

布伦特，非常感谢。想知道我的方法有什么问题？上限应该位于小或小的+1，下限应该位于小的或小的-1？谢谢。 –

嗨布伦特，我认为在上一步中发现的价值可能比小的大？假设在最后一步中，大小和中值相等且值>中（或小或大），但自从我们从中点+1开始移动后，值应小于中值+ 1？如果我错了，请随时纠正我。 :) –

当'my_list [mid]

这不是是简单。您必须考虑到以下事实：算法可能会从左侧（较低值）或右侧（较高值）逼近搜索项的位置，这在退出while回路后无法确定。因此，你必须检查在mid的值是否大于关键更小或更大：

lower = (my_list[mid] < key ? my_list[mid] : my_list[mid - 1]); 
upper = (my_list[mid] > key ? my_list[mid] : my_list[mid + 1]);

来源

2015-10-07 22:00:00 Paul

嗨保罗，为什么不检查中+ 1？ –

哦，先生，我应该在发布前仔细阅读答案。我会更正这个 – Paul

嗨保罗，那么我的方法有什么问题？上限应该位于小或小的+1，下限应该位于小的或小的-1？谢谢。 –

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

回答

相关问题