看起来有二种搜索的八种变体(按升序给出一个排序列表):
-
最小数量小于目标(但最重复的是)
-
最小数量小于目标(但最重要的是重复数字)
-
小于或等于目标的最大数字(但最重要的是最重要的)
-
小于或等于目标的最大数字(但最重要的是重复数字)
-
大于目标的最小数字(但最重复的是最左边的)
-
大于目标的最小数字(但最重要的是重复数字)
-
大于或等于目标的最小数字(但最重要的是最重要的)
-
大于或等于目标的最小数字(但最重要的是重复数字)
我如何知道如何正确和逻辑地为这些设置正确的二进制搜索类型?每当我尝试时,似乎逻辑往往会在列表变得非常小或者出现奇怪的边缘情况时失败,这让我觉得我的逻辑错误 .
是否有更好的方法从逻辑上考虑这种问题,以便更好地设置二进制搜索?
你总是听说很高比例的程序员如何不能正确地编写二进制搜索,但是我发现没有关于如何正确设置这8个案例的详尽文献我并不感到惊讶 .
1 回答
我用于二元搜索的心理模型如下:假设我们有一个单调递增的函数f:[a,b] - > {0,1}我们想从[a,b]中找到最小的数字i f(i)= 1,如果不存在这样的数字则为b . 以下算法将计算该结果:
最后,lo = hi = i .
有趣的是,这段代码永远不会检查f(b),所以如果只在[a,b-1]上定义f就没问题 . 如果f(b-1)= 0,则代码将报告b作为答案 . 只需使用正确的函数f,就可以涵盖使用此功能提到的所有情况 . 例如:
假设你有一个大小为n的数组 .
使用a = 0,b = n,f(i)= array [i]> = target
使用a = -1,b = n - 1,f(i)=(array [i 1]> = target) .
或者,使用(7)的解决方案并减去1.应该清楚的是,我们在这里只是将所有内容都移动了1 .
如果我没弄错的话,这需要两次搜索 . 您可以使用case(1)的解决方案(比如索引i),然后使用a = 0,b = i,f(j)= array [j] == array [i]来查找最左边的副本 .
等等
因为我已经开始使用这种模式,所以我认为我从未犯过二分搜索错误 .