【算法浅谈】二分法

二分法注意边界的开闭，以及除法自动取整的特性。

public int mySqrt(int x) {
        //使用简单二分法进行排除得出开方结果
        int ans = 0;
        //对输入为0的情况单独考虑
        if(x == 0) return x;
        //当输入不为0时，在[1,x]之间不断二分，当得到的结果的平方
        int left = 1,right = x;
        while(left<=right){
            mid = left + (right-left)/2;  //如果商为小数则默认取整
            if(sqrt==mid) return mid;
            else if(mid > sqrt){
                //目的是希望ans与sqrt尽可能接近，故当ans更大时，就应该在ans的左边设置新区间
                //又由于ans本身如果不能与sqrt相等的话，就会导致最终不满足循环条件，则应该取其右边的数，因为ans是取小的结果
                right = mid - 1;
            }else{
                left = mid + 1;
            }
        }
}

下面是一个很好的二分解释视频 和 模板

（图片来自B站视频 ​​二分查找怎么总是写错​​ ）

其实很多用到二分的问题就是在找蓝红的边界（该边界即为图中的K索引或者K-1索引）。下面写一下该视频采取的求解思路，左闭右闭？

模板

这里需要从数学的角度来理解这个模板，它的思想在于m是用于寻找边界的指针，需要由l和r共同决定其值，考虑到一些特殊情况，所以m必须满足[0,N)以内,也即m∈[0,N]，保证可以遍历到给定数组的所有元素。而循环退出条件之所以设置为l+1是否等于r，则表明在l和r相邻时退出循环，此时所要寻找的边界要么选取 l 要么选取 r 即可。

步骤：

1. 根据题意划分蓝红区域
2. 根据蓝红区域的划分设置isBlue的条件（即蓝色区间满足的条件）
3. 根据题目需要选择返回值

例子：

实践案例： ​​力扣第34题​​

搜索旋转排序数组
定义如下：

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。
（PS:旋转后其实就是类似两个排好序的数组合并）
来源：力扣（LeetCode）
链接：​​​https://leetcode.cn/problems/search-in-rotated-sorted-array​​