【算法】二分典型题

lc69 x的平方根

实现 int sqrt(int x) 函数。

计算并返回 x 的平方根，其中 x 是非负整数。

由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

code

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

还可以用牛顿迭代法公式求x的k次方根

class Solution {
    public int mySqrt(int x) {
        if (x == 0) {
            return 0;
        }

        double C = x, x0 = x;
        while (true) {
            double xi = 0.5 * (x0 + C / x0);
            if (Math.abs(x0 - xi) < 1e-7) {
                break;
            }
            x0 = xi;
        }
        return (int) x0;
    }
}

lc704 二分查找

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。


示例 1:

输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4

code

class Solution {
    public int search(int[] nums, int target) {
        int n = nums.length;
        int l = 0, r = n - 1;
        while(l < r){
            int mid = l + r + 1 >> 1;
            if(nums[mid] <= target)l = mid;
            else r = mid - 1;
        }
        if(nums[r] != target)return -1;
        return r ;
    }
}