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

二分主要就是判断上下边界

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

return 左侧还是右侧不是逻辑判断的结果吗

二分查找有几种写法？它们的区别是什么？ - 胖君的回答 - 知乎
https://www.zhihu.com/question/36132386/answer/155438728 二分查找有几种写法？它们的区别是什么？ - 胖君的回答 - 知乎
https://www.zhihu.com/question/36132386/answer/155438728

二分直接记住 lowerbound 和 upperbound 的手写，然后把条件转化往里套

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

还有一种是固定二分的次数，只要次数足够多，那解的精度一般足够靠谱

@Caturra 对于普遍的边界问题,有什么方法论吗?

搜一下科班讲 loop invariant 的 ppt 看，逼乎就算了

我觉得记录 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 可以很容易地按这样写出二分

v2 的评论里贴代码真是蛋疼...有啥好办法吗

代码:
https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=477f0db729449ca41f820adbfea19621

@mortonnex 注意细节就好了吧😅，常见的像区间上[l,r)还是[l,r]，区间长 r-l 还是 r-l+1 确实很容易搞错

@rayingecho 我想了你这个想了好久，感觉 size - half 这个地方安全性还是很难保证呀，然后 mid 的位置好像每次也不太一样，size == 1 退出也没想明白， 能通过感觉很玄学了。然后只调节 base 又很多功能实现不了，比如 lower_bound 这种。

@lhx2008
half 是 size / 2, size 到 1 退出是因为结果集只剩一个结果了, 那么只有两种情况, 这个结果就是解 or 没有解
调节 base 和调节两个指针其实是一样的, 因为 size 也在变, 不过 lower_bound 是什么意思?

@rayingecho lower_bound 是 大于等于 X 的最小值的下标，比如 [1,3,5,7,9] 找 6，返回 7 的下标
你这个思路要怎么写呢。

8 的平方根是.....2 ？

@Yanni0507 准确来说是求小于等于 8 平方根的最大整数

@lhx2008
等于说要找出 x 的插入位置保持数组有序对吧? 这个需要在最后判断一次 vec[base] 是否小于 x

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