首页 文章

如何逻辑地解释二进制搜索的任何变化

提问于
浏览
4

看起来有二种搜索的八种变体(按升序给出一个排序列表):

  • 最小数量小于目标(但最重复的是)

  • 最小数量小于目标(但最重要的是重复数字)

  • 小于或等于目标的最大数字(但最重要的是最重要的)

  • 小于或等于目标的最大数字(但最重要的是重复数字)

  • 大于目标的最小数字(但最重复的是最左边的)

  • 大于目标的最小数字(但最重要的是重复数字)

  • 大于或等于目标的最小数字(但最重要的是最重要的)

  • 大于或等于目标的最小数字(但最重要的是重复数字)

我如何知道如何正确和逻辑地为这些设置正确的二进制搜索类型?每当我尝试时,似乎逻辑往往会在列表变得非常小或者出现奇怪的边缘情况时失败,这让我觉得我的逻辑错误 .

是否有更好的方法从逻辑上考虑这种问题,以便更好地设置二进制搜索?

你总是听说很高比例的程序员如何不能正确地编写二进制搜索,但是我发现没有关于如何正确设置这8个案例的详尽文献我并不感到惊讶 .

1 回答

  • 3

    我用于二元搜索的心理模型如下:假设我们有一个单调递增的函数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]> = target

    (1)最大数量小于目标(但最重要的是重复)

    使用a = -1,b = n - 1,f(i)=(array [i 1]> = target) .

    或者,使用(7)的解决方案并减去1.应该清楚的是,我们在这里只是将所有内容都移动了1 .

    (2)最大数量小于目标(但最重要的是)

    如果我没弄错的话,这需要两次搜索 . 您可以使用case(1)的解决方案(比如索引i),然后使用a = 0,b = i,f(j)= array [j] == array [i]来查找最左边的副本 .

    等等

    因为我已经开始使用这种模式,所以我认为我从未犯过二分搜索错误 .

相关问题