给自己复盘用的随想录笔记day1-二分查找

二分法

使用情景

数组为有序数组，同时题目还强调数组中无重复元素，因为一旦有重复元素，使用二分查找法返回的元素下标可能不是唯一的，这些都是使用二分法的前提条件，当大家看到题目描述满足如上条件的时候，可要想一想是不是可以用二分法了。

求某一个整数的平方根

边界条件

写二分法，区间的定义一般为两种，左闭右闭即[left, right]，或者左闭右开即[left, right)。

区间的定义就是不变量，那么在循环中坚持根据查找区间的定义来做边界处理，就是循环不变量规则。

相关题目

搜索插入位置

public int searchInsert(int[] nums, int target) {
    int left = 0;
    int right = nums.length;
    while (left < right) { //左闭右开 [left, right)
        int middle = left + ((right - left) >> 1);
        if (nums[middle] > target) {
            right = middle; // target 在左区间，在[left, middle)中
        } else if (nums[middle] < target) {
            left = middle + 1; // target 在右区间，在 [middle+1, right)中
        } else { // nums[middle] == target
            return middle; // 数组中找到目标值的情况，直接返回下标
        }
    }
    // 目标值在数组所有元素之前 [0,0)
    // 目标值插入数组中的位置 [left, right) ，return right 即可
    // 目标值在数组所有元素之后的情况 [left, right)，因为是右开区间，所以 return right
    return right;
}

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

这个左右边界的思想分别左右滑动寻找左边界右边界，我觉得这个思路最好理解

class Solution {
	public int[] searchRange(int[] nums, int target) {
		int index = binarySearch(nums, target); // 二分查找
		
		if (index == -1) { // nums 中不存在 target，直接返回 {-1, -1}
			return new int[] {-1, -1}; // 匿名数组 
		}
		// nums 中存在 target，则左右滑动指针，来找到符合题意的区间
		int left = index;
		int right = index;
        // 向左滑动，找左边界
		while (left - 1 >= 0 && nums[left - 1] == nums[index]) { // 防止数组越界。逻辑短路，两个条件顺序不能换
			left--;
		}
        // 向右滑动，找右边界
		while (right + 1 < nums.length && nums[right + 1] == nums[index]) { // 防止数组越界。
			right++;
		}
		return new int[] {left, right};
    }
	
	/**
	 * 二分查找
	 * @param nums
	 * @param target
	 */
	public int binarySearch(int[] nums, int target) {
		int left = 0;
		int right = nums.length - 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 -1; // 不存在
	}
}

上面这种思路是利用左右两个指针，如果简单的使用二分法的思路去解决这个问题，就是把这个问题分为两部分，先去求第一次出现目标值的位置，这个位置特点是前面的值都比目标值小；同理再去求最后一次出现目标值的位置，这个位置的特点是后面的都比目标值大

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int left = searchLeft(nums,target);
        int right = searchRight(nums,target);
        return new int[]{left,right};
    }
    public int searchLeft(int[] nums,int target){
        // 寻找元素第一次出现的地方
        int left = 0;
        int right = nums.length-1;
        while(left<=right){
            int mid = left+(right-left)/2;
            // >= 的都要缩小 因为要找第一个元素
            if(nums[mid]>=target){
                right = mid - 1;
            }else{
                left = mid + 1;
            }
        }
        // right = left - 1
        // 如果存在答案 right是首选
        if(right>=0&&right<nums.length&&nums[right]==target){
            return right;
        }
        if(left>=0&&left<nums.length&&nums[left]==target){
            return left;
        }
        return -1;
    }

    public int searchRight(int[] nums,int target){
        // 找最后一次出现
        int left = 0;
        int right = nums.length-1;
        while(left<=right){
            int mid = left + (right-left)/2;
            // <= 的都要更新 因为我们要找最后一个元素
            if(nums[mid]<=target){
                left = mid + 1;
            }else{
                right = mid - 1;
            }
        }
        // left = right + 1
        // 要找最后一次出现 如果有答案 优先找left
        if(left>=0&&left<nums.length&&nums[left]==target){
            return left;
        }
        if(right>=0&&right<=nums.length&&nums[right]==target){
            return right;
        }
        return -1;
    }
}

x的平方根

这个地方用的是二分法的思想，一定不要把数组的二分法的代码直接套用。

我们可以使用「二分查找」来查找这个整数，不断缩小范围去猜。

猜的数平方以后大了就往小了猜；
猜的数平方以后恰恰好等于输入的数就找到了；
猜的数平方以后小了，可能猜的数就是，也可能不是

69. x 的平方根 - 力扣（LeetCode）

public class Solution {

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

        int left = 1;
        int right = x / 2;
        while (left < right) {
            int mid = left + (right - left + 1) / 2;
            if (mid > x / mid) {
                right = mid - 1;
            } else if (mid == x / mid) {
                // 由于本题特殊性，如果 mid == x / mid 就找到了答案，其它问题不一定可以这样
                return mid;
            } else {
                left = mid;
            }
        }
        return left;
    }
}

一个整数的平方根肯定不会超过它自己的一半，但是 0 和 1 除外，因此我们可以在 1 到输入整数除以 2 这个范围里查找我们要找的平方根整数。0 单独判断一下就好。

问题：mid 为什么要加 1？

上面那个理解有点麻烦，其实就单纯的从数学问题去理解，写成闭区间的形式去分析。

public class Solution {

    public int mySqrt(int x) {
    if(x==0){
        return 0;
    }
    if(x==1){
        return 1;
    }
    
    int l=1;
    int r=x/2;
    while(l<=r){
        int m=l+(r-l)/2;
        if(x/m<m){
        r=m-1;
        }else if(x/m==m){
            return m;
        }else{
            l=m+1;
        }
    }
    return l-1;
    }
}

有效数的完全平方根

这个题目可以利用数学知识解题

class Solution {
    public boolean isPerfectSquare(int num) {
        // 1 + 3 + 5 + ... + (2 * n - 1) = (2 * n - 1 + 1) * n = n * n
        for(int i=1;num>0;i+=2)
            num -= i;
        return num == 0;
    }
}

反正哪一种方法记的快方便理解就背那个方法，要刷算法题目