一文带你吃透二分查找法

前言

`

二分法的原理本身是很简单的，但是在实际场景中却总是有着各种各样的边界问题，此文章为y哥学习笔记。

一、二分法使用场景

当问题存在以下特征时，往往可以利用二分法进行求解。
1、具有单调性（70%）
2、答案区间具有两段性。（95%）一段满足题设，一段不满足。边界会有两个（前端边界点为A和后端边界点为B）

二、二分法模板

根据上图分析可总结出两套代码模板（JS）
模板一:

function bsearch_1(l, r)
{
    while (l < r)
    {
        var mid = l + r  >> 1;
        if (check(mid)) r = mid;
        else l = mid+1;
    }
    return l;
}

模板二:

function bsearch_2(l, r)
{
    while (l < r)
    {
        var mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return r;
}

二、二分法例题

1、69. x 的平方根

该题按照以下步骤去分析：
1、确定二分边界：
根据题目所述，其答案区间应该为非负整数，即0~x
2、确定check函数：
想要正确的写出二分代码的框架（即正确选择模板）需要对此问题细细分析，这个过程也就是选择模板的过程，那么先要确定一个check函数，这个函数是可以使区间分成两段（且使这个边界为答案，check(答案)===true.回到这个问题，设最终答案为t，则check函数应为t^2<=x；为什么这么取呢？因为最终的答案是一个向下取整的，如果是t*t>=x,无法区分成两段区间，如下图所示：

2、确定模板：
将区间划分好之后，就可以去确定模板，若为右边界则利用模板二；若为左边界则利用模板一，该题应该使用模板二，因为最终结果是右边界。模板带入即可。
3、最终代码：
按照上述方法很轻松就可以写出答案：

/**
 * @param {number} x
 * @return {number}
 */
var mySqrt = function(x) {
    let l=0;
    let r=x;
    while(l<r){
        let mid=l+r+1>>1
        if(mid<=x/mid){
              l=mid  
        }else{
            r=mid-1
        }
    }
    return r
};

2.搜索插入位置

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var searchInsert = function(nums, target) {
    if(nums.length===0||nums[nums.length-1]<target) return nums.length
     let l=0;
     let r=nums.length-1;
     while(l<r){
         let m=l+r>>1
         if(nums[m]>=target) r=m
         else l=m+1
     }
     return l
};

3.第一个错误的版本

/**
 * Definition for isBadVersion()
 * 
 * @param {integer} version number
 * @return {boolean} whether the version is bad
 * isBadVersion = function(version) {
 *     ...
 * };
 */

/**
 * @param {function} isBadVersion()
 * @return {function}
 */
var solution = function(isBadVersion) {
    /**
     * @param {integer} n Total versions
     * @return {integer} The first bad version
     */
    return function(n) {
        let l=1;
        let r=n;
        while(l<r){
            let mid=l+r>>1
            if(isBadVersion(n)) r=mid
            else l=m+1
        }
        return l
    };
};

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

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var searchRange = function(nums, target) {
    let l=0;
    let r=nums.length-1;
    while(l<r){
        let mid=l+r>>1
        if(nums[mid]>=target) r=mid
        else l=mid+1
    }
    if(target!==nums[r]) return [-1,-1]
    let left=r
    l=0;r=nums.length-1
    while(l<r){
        let mid=l+r+1>>1
        if(nums[mid]<=target) l=mid
        else r=mid-1
    }
    return [left,l]
};

5.搜索二维矩阵

这道题虽然是middle级别，但是按照上述的过程：找范围->分区间（确定check函数）->套模板 即可轻松完成，这里再大概简述一下每一步所完成的工作。
1、找范围：
设矩阵有n行，m列。n=matrix.length；m=matrix[0].length
则该矩阵总共有元素 nm-1个
范围则为0~nm-1
2、分区间（确定check函数）
这里要找到一个函数，使得区间可以完整分成两部分，并且该函数分 的区间边界点也是满足check函数，即check（边界点）===true，这里check函数的形式一般写出f(t)= x，t则是mid所代表的那个数字，x则为区间中的数字。在这道题，我设置的check函数为t<=x,划分的区间如下：

此时蓝色区域则都满足t<=x，绿色区域则不可以满足。实现二分性。
3、最后直接套用模板即可，最终代码如下：

/**
 * @param {number[][]} matrix
 * @param {number} target
 * @return {boolean}
 */
var searchMatrix = function(matrix, target) {
    if(matrix.length===0||matrix[0].length===0) return false
    let l=0
    let n=matrix.length;
    let m=matrix[0].length
    let r=n*m-1
    while(l<r){
        let mid=l+r+1>>1
        if(matrix[Math.floor(mid/m)][mid%m]<=target) l=mid
        else r=mid-1
    }   
    if(matrix[Math.floor(r/m)][r%m]!=target) return false
    return true
};

6.寻找旋转排序数组中的最小值

依旧是按照刚才的思路，对于此题比较难确定的是check函数应该如何设定才能将区间区分成二段区间。这里可以观察一下旋转数组的特点：

可以将函数设置为nums[t]<数组的最后一个数，这样求出来的左边界点就是最终的答案，具体代码如下

/**
 * @param {number[]} nums
 * @return {number}
 */
var findMin = function(nums) {
    let l=0
    let r=nums.length-1
    while(l<r){
        let mid=l+r>>1
        if(nums[mid]<=nums[nums.length-1]) r=mid
        else l=mid+1
    }
    return nums[l]
};