二分进阶：搜索旋转排序数组

猜数字大小（LeetCode 374）

public int guessNumber(int n) {
    int lo = 1, hi = n;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        int res = guess(mid);   // -1: too high, 0: correct, 1: too low
        if (res == 0) return mid;
        else if (res < 0) hi = mid - 1;
        else lo = mid + 1;
    }
    return lo;
}

有效的完全平方数（LeetCode 367）

不用 sqrt，用二分判断。

public boolean isPerfectSquare(int num) {
    int lo = 1, hi = num;
    while (lo <= hi) {
        long mid = lo + (hi - lo) / 2;
        long sq = mid * mid;
        if (sq == num) return true;
        else if (sq < num) lo = (int) mid + 1;
        else hi = (int) mid - 1;
    }
    return false;
}

x 的平方根（LeetCode 69）

public int mySqrt(int x) {
    int lo = 0, hi = x;
    while (lo < hi) {
        long mid = lo + (hi - lo + 1) / 2;  // 上取整防止死循环
        if (mid * mid <= x) lo = (int) mid;
        else hi = (int) mid - 1;
    }
    return lo;
}

注意：hi = x 须用 long 避免溢出；上取整是因为要找"最大满足 mid² ≤ x"的右边界。

两个有序数组的中位数（LeetCode 4）

这是二分查找最难的变体，已在 03-binary-search-matrix 中详细讲解，这里给精简要点：

1. 保证在较短数组中二分（if m > n: swap）
2. 分割点平衡：i + j = (m + n + 1) / 2
3. 边界处理：i = 0 时 maxLeft1 = -∞，i = m 时 minRight1 = +∞
4. 循环终止条件：maxLeft1 <= minRight2 && maxLeft2 <= minRight1

Pow(x, n)（LeetCode 50）

二分（快速幂）：

public double myPow(double x, int n) {
    long N = n;
    if (N < 0) { x = 1.0 / x; N = -N; }
    return fastPow(x, N);
}

private double fastPow(double x, long n) {
    if (n == 0) return 1.0;
    double half = fastPow(x, n / 2);
    return n % 2 == 0 ? half * half : half * half * x;
}

总结