V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
lhx2008
V2EX  ›  问与答

二分查找的算法题如何考虑到各种情况不出问题呢?

  •  
  •   lhx2008 · 2019-02-18 12:09:39 +08:00 · 1492 次点击
    这是一个创建于 2092 天前的主题,其中的信息可能已经有所发展或是发生改变。
    假设不能用 IDE Debug

    比如 x 的 平方根这种题,要考虑到舍去的情况( 8 的平方根是 2 ),最后面 return l 还是 r,while 的条件是 <= 还是 < ,这种怎么考虑呢,或者有什么规律吗?


    写到纸上也很容易乱,而且至少也要测试 2 4 8 几种情况,如果之前定的策略不对还要调整
    15 条回复    2019-02-18 19:00:51 +08:00
    zcjfesky
        1
    zcjfesky  
       2019-02-18 13:27:11 +08:00 via Android
    二分主要就是判断上下边界

    单个区间下边界<=上边界且 A 区间的上边界不和 B 区间的下边界交叉,基本就差不多了

    return 左侧还是右侧不是逻辑判断的结果吗
    mortonnex
        2
    mortonnex  
       2019-02-18 13:40:02 +08:00   ❤️ 1
    二分查找有几种写法?它们的区别是什么? - 胖君的回答 - 知乎
    https://www.zhihu.com/question/36132386/answer/155438728 二分查找有几种写法?它们的区别是什么? - 胖君的回答 - 知乎
    https://www.zhihu.com/question/36132386/answer/155438728
    Caturra
        3
    Caturra  
       2019-02-18 13:55:03 +08:00   ❤️ 2
    二分直接记住 lowerbound 和 upperbound 的手写,然后把条件转化往里套

    你可以把二分写成求最小的 l 使 l 平方大于等于 x,这里不就能往里套了吗

    还有一种是固定二分的次数,只要次数足够多,那解的精度一般足够靠谱
    mortonnex
        4
    mortonnex  
       2019-02-18 14:45:27 +08:00
    @Caturra 对于普遍的边界问题,有什么方法论吗?
    lance6716
        5
    lance6716  
       2019-02-18 15:05:31 +08:00 via Android
    搜一下科班讲 loop invariant 的 ppt 看,逼乎就算了
    rayingecho
        6
    rayingecho  
       2019-02-18 15:24:57 +08:00
    我觉得记录 lower 和 upper 两个下标的二分写法考虑边界条件有点不直观, 所以一般都用维护一个解空间大小和一个下标的办法来写, 比如 x 的平方根:

    pub fn sqrt(num: i32) -> i32 {
    let mut size = num;
    let mut base = 1;
    while size > 1 {
    let half = size / 2;
    let mid = base + half;
    // 判断目标解在哪一半
    if mid * mid <= num {
    base = mid;
    }
    size -= half;
    }
    base
    }

    这种写法对我而言非常直观, 反正就是每次循环将解空间砍掉一半, 砍掉一半时需要判断目标解在哪个半边中, 对于这个问题, 我们希望找到的是 max i 使 i^2 <= num, 所以假如 mid^2 > num, 则目标解在前半部分, 反之在后半部分

    这种思考方式确实能简化问题, 比如 leetcode 的 #33 search in rotated sorted array 可以很容易地按这样写出二分
    rayingecho
        7
    rayingecho  
       2019-02-18 15:25:22 +08:00
    v2 的评论里贴代码真是蛋疼...有啥好办法吗
    Caturra
        9
    Caturra  
       2019-02-18 16:11:19 +08:00 via Android
    @mortonnex 注意细节就好了吧😅,常见的像区间上[l,r)还是[l,r],区间长 r-l 还是 r-l+1 确实很容易搞错
    lhx2008
        10
    lhx2008  
    OP
       2019-02-18 17:34:51 +08:00
    @rayingecho 我想了你这个想了好久,感觉 size - half 这个地方安全性还是很难保证呀,然后 mid 的位置好像每次也不太一样,size == 1 退出也没想明白, 能通过感觉很玄学了。然后只调节 base 又很多功能实现不了,比如 lower_bound 这种。
    rayingecho
        11
    rayingecho  
       2019-02-18 17:39:44 +08:00
    @lhx2008
    half 是 size / 2, size 到 1 退出是因为结果集只剩一个结果了, 那么只有两种情况, 这个结果就是解 or 没有解
    调节 base 和调节两个指针其实是一样的, 因为 size 也在变, 不过 lower_bound 是什么意思?
    lhx2008
        12
    lhx2008  
    OP
       2019-02-18 17:43:58 +08:00
    @rayingecho lower_bound 是 大于等于 X 的最小值的下标,比如 [1,3,5,7,9] 找 6,返回 7 的下标
    你这个思路要怎么写呢。
    Yanni0507
        13
    Yanni0507  
       2019-02-18 17:45:50 +08:00
    8 的平方根是.....2 ?
    lhx2008
        14
    lhx2008  
    OP
       2019-02-18 17:53:24 +08:00 via Android
    @Yanni0507 准确来说是求小于等于 8 平方根的最大整数
    rayingecho
        15
    rayingecho  
       2019-02-18 19:00:51 +08:00   ❤️ 1
    @lhx2008
    等于说要找出 x 的插入位置保持数组有序对吧? 这个需要在最后判断一次 vec[base] 是否小于 x

    https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=a6854ce2b7b9e5305628dd6af561f600
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2697 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 24ms · UTC 06:44 · PVG 14:44 · LAX 22:44 · JFK 01:44
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.