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

2019-02-18 12:09:39 +08:00
 lhx2008
假设不能用 IDE Debug

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


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

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

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

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

还有一种是固定二分的次数,只要次数足够多,那解的精度一般足够靠谱
mortonnex
2019-02-18 14:45:27 +08:00
@Caturra 对于普遍的边界问题,有什么方法论吗?
lance6716
2019-02-18 15:05:31 +08:00
搜一下科班讲 loop invariant 的 ppt 看,逼乎就算了
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
2019-02-18 15:25:22 +08:00
v2 的评论里贴代码真是蛋疼...有啥好办法吗
rayingecho
2019-02-18 15:29:20 +08:00
Caturra
2019-02-18 16:11:19 +08:00
@mortonnex 注意细节就好了吧😅,常见的像区间上[l,r)还是[l,r],区间长 r-l 还是 r-l+1 确实很容易搞错
lhx2008
2019-02-18 17:34:51 +08:00
@rayingecho 我想了你这个想了好久,感觉 size - half 这个地方安全性还是很难保证呀,然后 mid 的位置好像每次也不太一样,size == 1 退出也没想明白, 能通过感觉很玄学了。然后只调节 base 又很多功能实现不了,比如 lower_bound 这种。
rayingecho
2019-02-18 17:39:44 +08:00
@lhx2008
half 是 size / 2, size 到 1 退出是因为结果集只剩一个结果了, 那么只有两种情况, 这个结果就是解 or 没有解
调节 base 和调节两个指针其实是一样的, 因为 size 也在变, 不过 lower_bound 是什么意思?
lhx2008
2019-02-18 17:43:58 +08:00
@rayingecho lower_bound 是 大于等于 X 的最小值的下标,比如 [1,3,5,7,9] 找 6,返回 7 的下标
你这个思路要怎么写呢。
Yanni0507
2019-02-18 17:45:50 +08:00
8 的平方根是.....2 ?
lhx2008
2019-02-18 17:53:24 +08:00
@Yanni0507 准确来说是求小于等于 8 平方根的最大整数
rayingecho
2019-02-18 19:00:51 +08:00
@lhx2008
等于说要找出 x 的插入位置保持数组有序对吧? 这个需要在最后判断一次 vec[base] 是否小于 x

https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=a6854ce2b7b9e5305628dd6af561f600

这是一个专为移动设备优化的页面(即为了让你能够在 Google 搜索结果里秒开这个页面),如果你希望参与 V2EX 社区的讨论,你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://www.v2ex.com/t/536060

V2EX 是创意工作者们的社区,是一个分享自己正在做的有趣事物、交流想法,可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX