【D21】搜索插入位置&x 的平方根（LC 35&69）

今日主题：二分查找。

35. 搜索插入位置

问题描述

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
你可以假设数组中无重复元素。

解题思路

两端都闭的二分查找。

代码实现

class Solution {
    public int searchInsert(int[] nums, int target) {
        int len = nums.length;
        int left = 0, right = len -1;

        while(left <= right){
            int mid = left + (right - left) / 2;
            if(nums[mid] == target){
                return mid;
            }else if(nums[mid] < target){
                //右侧
                left = mid + 1;
            }else {
                //左侧
                right = mid - 1;
            }
        }
        return left;

    }
}

69. x 的平方根

问题描述

实现 int sqrt(int x) 函数。
计算并返回 x 的平方根，其中 x 是非负整数。
由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

解题思路

由于 x 平方根的整数部分是满足 k^2 ≤x 的最大 k 值，因此我们可以对 k 进行二分查找，从而得到答案。

• 注意处理大整形求平方时的整形溢出问题

代码实现

class Solution {
    public int mySqrt(int x) {
        if(x < 2){
            //0的平方根是0
            return x;
        }
        long left = 1, right = x;
        while(left <= right){
            long mid = left + (right - left) / 2;
            long sqrt = mid * mid;
            if(sqrt == x){
                return (int) mid;
            }else if(sqrt < x){
                left = mid + 1;
            }else {
                right = mid - 1;
            }
        }

        return (int) left - 1 ;   

    }
}