二分法使用小总结

二分法是我们在进行算法练习时经常遇到的一种题目的类型，但是关于二分，你真的真的会用吗？

那些年搞不清楚的区间定义

当我们面对一个有序的数组时，我们首先要考虑是不是可以用二分法来解决相应的问题。但是二分法虽然用起来简便，理解起来也相对地容易。但是我们在最初开始使用的时候，往往会出现各种各样的问题，例如while中的终止条件到底应该时<还是<=呢？left和right重新定义时，到底是=mid还是=mid+1呢？判断不好这些问题，我们的代码往往就会出现各种的bug，甚至还会出现死循环的问题。

那么如何解决这个问题呢？最重要的就是要理解二分在使用过程中的区间定义

网上有很多关于二分法的一些模板，但是死记硬背不是解决问题的根本方法；理解它其实很简单，只需要一句话，就是判断的时候想想我们的区间是否有效

 //针对于数组nums
    let left = 0;
    let right = nums.length  //因为我们不可能取到值为nums.length的下标，所以此时区间应为[left,right)
    while(left < right)    //为什么不取等号的原因是 当left = right 时，区间就会像这样[1,1)，区间是无效的不需要执行代码
      
    let left = 0;
    let right = nums.length - 1  //此时区间应为[left,right]
    while(left <= right)    //当left = right 时，区间就会像这样[1,1]，区间依然是有效的，继续执行代码

现在就搞懂了到底有等于还是没有等于号的问题了，不过一般大家都比较推荐[left,right)的形式，这样可以避免死循环，不过只要你的思路清晰，哪一种都是ok的。

继续来看一个例子，来看看什么时候+1，什么时候不需要+1

35. 搜索插入位置 – 力扣（LeetCode） (leetcode-cn.com)

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

var searchInsert = function(nums, target) {
    let left = 0;
    let right = nums.length
    while(left < right){  //此时区间为[left,right)
        let mid = Math.floor((left+right)/2)
        if(nums[mid]===target) return mid
        if(nums[mid] < target) left = mid + 1;  //当nums[mid] < target，这个mid已经不满足条件了，同时left是在区间中的，所以需要mid + 1
        if(nums[mid] > target) right = mid;  //当nums[mid] > target，这个mid已经不满足条件了，但right不在区间中，所只需要mid
    }
    return left;
};

如果懂了上面的代码，再来看

var searchInsert = function(nums, target) {
    let left = 0;
    let right = nums.length - 1
    while(left <= right){  //此时区间为[left,right]
        let mid = Math.floor((left+right)/2)
        if(nums[mid]===target) return mid
        if(nums[mid] < target) left = mid + 1;  //mid已经不满足条件了，同时left是在区间中的，所以需要mid + 1
        if(nums[mid] > target) right = mid - 1;  //mid已经不满足条件了，但right也在区间中，所以需要mid - 1
    }
    return left;
};

两段代码的效果是一样的

简而言之，就是根据left和right是否在区间中有效来判断是否需要+1或-1

但只是最简单的情况，不同题目还要具体的分析，其实只要理解了，再复杂的情况也能巧妙应对。

关于return left 还是right 的问题

在一些题目中，并不是一定可以找到我们的目标值，也就是没有mid满足条件的情况，这个时候题目往往会告诉我们，如果发生了这种情况我们需要返回什么，还是上面插入元素的例子，如果没有，我们就返回目标元素被插入的位置，或者是找平方根时，8 的平方跟不是整数就取2；

69. x 的平方根 – 力扣（LeetCode） (leetcode-cn.com)

const mySqrt = x => {
    let [left, right] = [0, x];
    while (left <= right) {
        const mid = Math.floor((left+right)/2);
        if (mid * mid > x) {
            right = mid - 1;
        } else if (mid * mid < x) {
            left = mid + 1;
        } else {
            return mid;
        }
    }
    return right;
};

可以注意到，在插入元素时，我们返回了left，而在这边返回了right。

其实这是没有是什么规律的，就算是同一道题，不同地代码返回的也可能时不一样的；唯一的解决办法，就是分析，而我一般会自己举一个例子，如这里的8的平方根，然后再画一张图，按照代码的流程走下去，最后你自然会发现返回的是哪个。

LeetCode中二分题目汇总

35. 搜索插入位置 – 力扣（LeetCode） (leetcode-cn.com)

上面已经写过代码了，这里就不浪费篇幅了

240. 搜索二维矩阵 II – 力扣（LeetCode） (leetcode-cn.com)

具体思路：总左下角开始，小于目标值row–，大于目标值col++

var searchMatrix = function(matrix, target) {
    let maxI = matrix.length - 1;
    let maxJ = matrix[0].length-1;
    let i = maxI;
    let j = 0; 
    while(i>=0 && j<=maxJ){
        let cur = matrix[i][j]
        if(cur<target)  j++
        else if(cur>target) i--
        else return true;
    }
    
    return false
};

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

具体思路：进行二分遍历先找到某一个目标值，然后向左、向右扩展

var searchRange = function(nums, target) {
    let [left,right,flag] = [0,nums.length,null]
    while(left < right){
        let mid = Math.floor((left+right)/2)
        if(nums[mid] === target){
            flag = mid;
            break;
        }
        else if(nums[mid]<target) left = mid + 1;
        else right = mid
    }
    if(flag == null) return [-1,-1]
    left = right = flag
    while(nums[left - 1] === target) left--;
    while(nums[right + 1] === target) right++;
    return [left,right]
};

162. 寻找峰值 – 力扣（LeetCode） (leetcode-cn.com)

具体思路：进行遍历，条件设置为mid是否大于mid+1；注意这里的left<right,否则会出现死循环的现象，被认为是怎么知道的。

var findPeakElement = function(nums) {
    let left = 0;
    let right = nums.length-1;
    while(left<right){
        let mid = Math.floor((left+right)/2)
        if(nums[mid]>nums[mid+1]) right = mid
        else left = mid + 1
    }
    return right
};

153. 寻找旋转排序数组中的最小值 – 力扣（LeetCode） (leetcode-cn.com)

具体思路：如果当前值小于最右边的值，最小值在mid左侧，也有可能是mid；如果当前值大于等于最右边的值，最小值在mid右侧，且不可能是mid

var findMin = function(nums) {
    let left = 0;
    let right = nums.length -1;
    while(left<=right){
        let mid = Math.floor((left+right)/2)
        if(nums[mid]<nums[right])  right = mid
        else left = mid + 1
    }
    return nums[right]
};

275. H 指数 II – 力扣（LeetCode） (leetcode-cn.com)

具体思路：最重要的要搞懂满足的条件是索引为mid的值要大于数组长度-mid，这样代表着满足条件，说明我们要找的值要么在它左边，要么就是它。但要注意的是最后的值是h，也就是不一定是我们数组中的某一个数，它只是代表着至少有几个。

var hIndex = function(citations) {
    const len = citations.length
    let left = 0;
    let right = len -1;
    let res = 0;
    while(left <= right){
        let mid = Math.floor((left+right)/2)
        if(citations[mid]>=(len - mid)){
            res = len - mid
            right = mid - 1 
        }else left = mid + 1
    }
    return res
};

300. 最长递增子序列 – 力扣（LeetCode） (leetcode-cn.com)

具体思路：维护一个数组，对原数组进行遍历，如果当前元素大于数组中最大的元素，那么直接放进去；如果小于或等于，那么在数组中找一个位置插进去。（要注意的是，被替换后形成的新数组未必是结果中正确的数组，但是长度一样，所以这道题二分法只是其中一种解法，并不可以说是最优解）

var lengthOfLIS = function(nums) {
    if(nums.length === 1) return 1;
    const arr = [nums[0]]
    for(let i = 1;i<nums.length;i++){
        if(nums[i]>Math.max(...arr)){
            arr.push(nums[i])
        }else{
            let left = 0
            let right = arr.length 
            while(left < right){
                let mid = Math.floor((right+left)/2)
                if(nums[i] > arr[mid]) left = mid + 1
                else right = mid 
                
            }
            arr[left] = nums[i]
        }
    }
    return arr.length

};

最后，当你做了一些题目之后，发现其实二分法并不难，重要的是理解题目的意思，搞明白二分法中的条件即可，灵活运用，方是真理！！！