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