二进制搜索似乎有八种变体（按升序排列列表）：
小于目标的最大数字（但重复项的最左侧）
小于目标的最大数字（但重复项的最右边）
小于或等于目标的最大数字（但重复项的最左侧）
小于或等于目标的最大数字（但重复项的最右边）
大于目标的最小数字（但重复项的最左侧）
大于目标的最小数字（但重复项的最右边）
大于或等于目标的最小数字（但重复项的最左侧）
大于或等于目标的最小数字（但重复项的最右边）
我怎么知道如何正确和逻辑地为这些设置正确的二进制搜索类型？每次尝试时，当列表变小或出现奇怪的边缘情况时，逻辑似乎都会失败，这使我认为我在错误地处理逻辑。
有没有更好的方法来从逻辑上考虑这种问题，以便可以更好地设置二进制搜索？
您总是会听到有很大比例的程序员无法正确编写二进制搜索代码的信息，但是我发现没有关于如何正确设置这8种情况的详尽文献，我一点都不感到惊讶。
我用于二分查找的思维模型如下：假设我们有一个单调递增的函数f：[a，b]-> {0,1}，我们想从[a，b]中找到最小的i f（i）= 1，或者b（如果不存在这样的数字）。以下算法将计算该结果：
lo = a, hi = b
while lo < hi:
# invariant: lo <= i <= hi
mid = (lo + hi)/2 # or lo + (hi - lo) / 2 to avoid overflows
if f(mid):
hi = mid
else:
lo = mid + 1
最后，lo = hi = i。
有趣的是，此代码永远不会检查f（b），因此，如果仅在[a，b-1]上定义f会很好。如果f（b-1）= 0，则代码将报告b作为答案。您只需使用正确的函数f，就可以涵盖您提到的所有情况。例如：
（7）大于或等于目标的最小数字（但重复项的最左侧）
假设您有一个大小为n的数组。
使用a = 0，b = n，f（i）= array [i]> =目标
（1）小于目标的最大数字（但重复项的最右边）
使用a = -1，b = n-1，f（i）=（数组[i + 1]> =目标）。
或者，将解决方案用于（7）并减去1。应该清楚的是，这里我们只是将所有内容都移位了1。
（2）小于目标的最大数字（但重复项的最左侧）
如果我没有记错的话，这需要两次搜索。您可以对情况（1）使用解决方案（例如索引i），然后使用a = 0，b = i，f（j）= array [j] == array [i]查找最左边的重复项。
等等
自从我开始使用这种模式以来，我认为我在二进制搜索中从未犯过错误。
京公网安备 11010802040832号 | 京ICP备19059560号-6 