1
zcjfesky 2019-02-18 13:27:11 +08:00 via Android
二分主要就是判断上下边界
单个区间下边界<=上边界且 A 区间的上边界不和 B 区间的下边界交叉,基本就差不多了 return 左侧还是右侧不是逻辑判断的结果吗 |
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 |
3
Caturra 2019-02-18 13:55:03 +08:00 2
二分直接记住 lowerbound 和 upperbound 的手写,然后把条件转化往里套
你可以把二分写成求最小的 l 使 l 平方大于等于 x,这里不就能往里套了吗 还有一种是固定二分的次数,只要次数足够多,那解的精度一般足够靠谱 |
5
lance6716 2019-02-18 15:05:31 +08:00 via Android
搜一下科班讲 loop invariant 的 ppt 看,逼乎就算了
|
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 可以很容易地按这样写出二分 |
7
rayingecho 2019-02-18 15:25:22 +08:00
v2 的评论里贴代码真是蛋疼...有啥好办法吗
|
8
rayingecho 2019-02-18 15:29:20 +08:00
|
9
Caturra 2019-02-18 16:11:19 +08:00 via Android
@mortonnex 注意细节就好了吧😅,常见的像区间上[l,r)还是[l,r],区间长 r-l 还是 r-l+1 确实很容易搞错
|
10
lhx2008 OP @rayingecho 我想了你这个想了好久,感觉 size - half 这个地方安全性还是很难保证呀,然后 mid 的位置好像每次也不太一样,size == 1 退出也没想明白, 能通过感觉很玄学了。然后只调节 base 又很多功能实现不了,比如 lower_bound 这种。
|
11
rayingecho 2019-02-18 17:39:44 +08:00
@lhx2008
half 是 size / 2, size 到 1 退出是因为结果集只剩一个结果了, 那么只有两种情况, 这个结果就是解 or 没有解 调节 base 和调节两个指针其实是一样的, 因为 size 也在变, 不过 lower_bound 是什么意思? |
12
lhx2008 OP @rayingecho lower_bound 是 大于等于 X 的最小值的下标,比如 [1,3,5,7,9] 找 6,返回 7 的下标
你这个思路要怎么写呢。 |
13
Yanni0507 2019-02-18 17:45:50 +08:00
8 的平方根是.....2 ?
|
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 |