Skip to content

二分猜答案

单调序列上找值

69. x 的平方根 mid

给你一个非负整数 x ,计算并返回 x 的 算术平方根。 由于返回类型是整数,结果只保留整数部分,小数部分将被舍去。

解法 1 二分

从一个单调序列上找一个值, 二分
m2<=target 的右边界

Java
class Solution {
    public int mySqrt(int x) {
        long l = 0, h = x;
        while (l < h) {
            long m = l + (h - l + 1 >> 1);
            if (m * m <= x) l = m;
            else h = m - 1;
        }
        return (int) l;
    }
}

解法 2 牛顿迭代法

C=x, 也就是求函数 y=f(x)=x2C 的零点
借助泰勒级数, 不断地求过 x0 点的切线与 x 轴的交点, 再求函数 f(x) 在交点横坐标处的切线, 直到 y 逼近 0
点: (x0,x02C)
切线: y(x02C)=2x0\*(xx0)
y=2x0xx02C
y=0,x=12(x0+Cx0)

java
class Solution {
    public int mySqrt(int x) {
        int c = x;
        double x0 = c;
        while (x0 * x0 - c > 1e6) {
            x0 = 0.5 * (x0 + c / x0);
        }
        return (int) x0;
    }
}

满足条件的上界/下界

875. 爱吃香蕉的珂珂 mid

剑指 Offer II 073. 狒狒吃香蕉

珂珂喜欢吃香蕉。这里有 n 堆香蕉,第 i 堆中有 piles[i]根香蕉。警卫已经离开了,将在 h 小时后回来。

珂珂可以决定她吃香蕉的速度 k (单位:根/小时)。每个小时,她将会选择一堆香蕉,从中吃掉 k 根。如果这堆香蕉少于 k 根,她将吃掉这堆的所有香蕉,然后这一小时内不会再吃更多的香蕉。

珂珂喜欢慢慢吃,但仍然想在警卫回来前吃掉所有的香蕉。

返回她可以在 h 小时内吃掉所有香蕉的最小速度 k(k 为整数)。

java
class Solution {
    public int minEatingSpeed(int[] piles, int h) {
        int r = Integer.MIN_VALUE;
        for (int e : piles) {
            r = Math.max(r, e);
        }
        int l = 1;
        while (l < r) {
            int m = l + (r - l >> 1);
            if (check(piles, h, m)) r = m;
            else l = m + 1;
        }
        return l;
    }

    private boolean check(int[] piles, int h, int k) {
        int sum = 0;
        for (int e : piles) {
            sum += (e + k - 1) / k;
        }
        return sum <= h;
    }
}