【力扣/代码随想录】数组

二分查找

704 二分查找

力扣

注意：
闭区间，所以while的条件是 <=
为了防止mid越界，使用 mid=(high-low)/2+low;
每次循环都要 更新mid

class Solution {
    public int search(int[] nums, int target) {
        int low=0;
        int high = nums.length-1;
        while(low<=high){
            int mid=(high-low)/2+low;
            if(nums[mid]<target){
                low = mid+1;
            }else if(nums[mid]>target){
                high = mid-1;
            }else if(nums[mid]==target){
                return mid;
            }
        }
        return -1;
    }
}

35 搜索插入位置

力扣

分析：

示例1
在范围内且存在：返回存在值的索引==》二分查找
示例2
在范围内但不存在：插入位置的索引
最终：high《low，high指向1，low指向3
上一次：high=low=mid指向3，》target，high=mid-1
示例3
不在范围内：超级小 0 /超级大 length
总结2、3：
mid一直是中间偏左（偶数个时），
所以会到【大于target的最左】，
然后high左移到【小于target的最右】
target放入 【小于target的最右=high】的下一个即可

class Solution {
    public int searchInsert(int[] nums, int target) {
        int left = 0, right = nums.length-1;
        while(left<=right){
            int mid = left+(right-left)/2;
            if(nums[mid]<target){
                left=mid+1;
            }else if(nums[mid]>target){
                right=mid-1;
            }else{
                return mid;
            }
        }
        return right+1;
    }
}

34 在排序数组中查找元素的第一个和最后一个位置

力扣

1、用二分查找确定是否存在
2、不存在：直接返回
3、存在：寻找左右边界
注意：
左右边界寻找时要注意是否越界，限制条件是leftBorder>0、rightBorder<nums.length-1，使用开区间限制左右边界，如果左右边界就是数组边界，不再寻找，否则可以同时保证探寻的更左、更右不越界。

class Solution {
    public int[] searchRange(int[] nums, int target) {
        /*
        二分查找 找到了确定开始和结束 没找到返回
        确定边界：左、右
        */

        int index = search(nums,target);
        if(index==-1){
            return new int[] {-1,-1};
        }else{
            //left
            int leftBorder=index;
            while(leftBorder>0 && nums[leftBorder]==nums[leftBorder-1]){
                leftBorder--;
            }

            //right
            int rightBorder=index;
            while(rightBorder<nums.length-1&&nums[rightBorder]==nums[rightBorder+1]){
                rightBorder++;
            }

            return new int[]{leftBorder,rightBorder};
        }

    }

    // 二分查找
    public int search(int[] nums, int target) {
        int low=0;
        int high = nums.length-1;
        while(low<=high){
            int mid=(high-low)/2+low;
            if(nums[mid]<target){
                low = mid+1;
            }else if(nums[mid]>target){
                high = mid-1;
            }else if(nums[mid]==target){
                return mid;
            }
        }
        return -1;
    }
}

69. x 的平方根

添加链接描述

k * k=x，只保留整数部分，k是满足k * k<=x的最大整数
所以要用 res保存当前的满足mid*mid<=x的mid，而不是直接使用mid，可能存在问题比如8的结果为3而不是2

class Solution {
    public int mySqrt(int x) {
        int low = 1;
        int high = x;
        int mid = (high - low) / 2 + low;
        int res = -1;
        if (x == 0)
            return 0;
        while (low <= high) {
            mid = (high - low) / 2 + low;
            if ((long) mid * mid <= x) {
                res = mid;
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return res;
    }
}

367. 有效的完全平方数

力扣

class Solution {
    public boolean isPerfectSquare(int num) {

        int low = 1;
        int high = num;

        while (low <= high) {
            int mid = (high - low) / 2 + low;
            if ((long) mid * mid < num) {
                low = mid + 1;
            } else if ((long) mid * mid > num)  {
                high = mid - 1;
            }else{
                return true;
            }
        }
        return false;
    }
}