这是一个创建于 2107 天前的主题，其中的信息可能已经有所发展或是发生改变。
假设不能用 IDE Debug
比如 x 的 平方根这种题，要考虑到舍去的情况（ 8 的平方根是 2 ），最后面 return l 还是 r，while 的条件是 <= 还是 < ，这种怎么考虑呢，或者有什么规律吗？
写到纸上也很容易乱，而且至少也要测试 2 4 8 几种情况，如果之前定的策略不对还要调整
比如 x 的 平方根这种题，要考虑到舍去的情况（ 8 的平方根是 2 ），最后面 return l 还是 r，while 的条件是 <= 还是 < ，这种怎么考虑呢，或者有什么规律吗？
写到纸上也很容易乱，而且至少也要测试 2 4 8 几种情况，如果之前定的策略不对还要调整
 |
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 |
Select Language