详解二分法

无论是工作中，生活中，刷题时，查找都是非常常见的场合，很多同学对于数组中查找某一元素，第一反应都是线性查找，即for循环从nums[0]遍历到nums[n-1]，这样时间复杂度是O(n)，如果是使用二分法不断折半区间的方法，时间复杂度仅为O(logn)，看似不高，当数据量较大时，我们来看一下俩者区别

很多超时问题是不是都有解决的思路了？

还有一些同学会二分法，但是一写就容易出错，据说能一次写对二分法的程序员只有10%。这是因为他们忽略了二分法的定义和一些细节，当遇到多变的场景时就容易在出错，本文将从二分法定义出发，给出二分法常见出错点，题目变化，以及应对方法，帮助大家下次写二分法时正确率能提高到90%！

维基百科二分法定义如下

在计算机科学中，二分查找算法也称折半搜索算法，对数搜索算法，是一种在有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。

第一句话我们抓住俩个关键词，一是有序数组（这里可能是整体有序比如[1,2,3,4,5]，也有可能是局部有序比如[4,5,1,2,3]），二是特定元素（也有可能是满足特定的条件）。由定义我们大概就知道了二分法的应用场景，在有序数组中找特定值都可以考虑用二分法。

第二句话说的是二分法的核心，每一次比较都使搜索范围缩小一半。文字比较绕，下面将通过一个案例，帮助大家进一步了解这句话

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

二分法题目都可以分下面三步

第一步确定是否满足二分法的使用条件，有序数组与查找特定元素，题目中nums有序，查找的是指定元素target，满足条件

第二步确定特定元素target的伪代码，这题比较简单就是nums[mid]==target

第三步确定边界的变化，根据定义的第二句话，写出代码如下

整个过程如下

nums[mid] //注意 mid := left + (right-left)>>1 if nums[mid] > target { right = mid - 1 //注意 } else if nums[mid] return mid } } return -1 }

再将代码进一步抽象成模板如下

二分法都是在这套模板上变形，外层的for循环以及left和right的变动是帮助我们不断的缩小范围，当满足条件nums[mid] == target时就可以退出循环，代码看似不难，但是易错点很多，试着独立思考下面这个问题。

循环条件写left mid := (left + right) >> 1 if nums[mid] return mid } else { right = mid } } return -1 }

希望不是很熟练的同学尽量一直使用left mid := (left + right) / 2 if (mid*mid x) || mid*mid == x { return mid } else if mid*mid right = mid - 1 } } return 0 四、带精度的二分 前言

带精度的二分比整数域二分要复杂一点，带精度的往往是给定一个精度范围，让你在精度范围中去找到这个数

实现 float64 sqrt(float64 x) 函数。

计算并返回 x 的平方根，其中 x 是非负浮点数。

返回精度为0.01的开方值

示例 2:

确定目标target和有序性：这题和第一题的区别就是多了一个精度，其他条件都是一样的，试想一下如果精度x是2的话，就可以理解为从数组[0.00，0.01，0.02…1.18，1.19，2]中去寻找到target，有序区间有了！当俩个边界落在0.01和0.02时，这时取值就在精度以下（重点），因此target条件是right-left < 0.01|| mid*mid == n

确定target伪代码：mid*mid==n（为了便于理解，例题target条件都很简单，但是这步必不可少）

确定边界变化，取到的mid不满足条件就可以排出在区间外了，所以边界值按+1，-1算，核心代码如下（写在草稿上）

最后贴上完整代码

精度的主要变化在for循环条件上，整数域可以理解为精度是0的带精度二分，整数域条件为right-left >= 0，也就是right>=left。

整数域二分和带精度的二分都是target条件的变化，那么从定义出发还有一个有序数组可以出题目了，这类题目一般是旋转数组变成局部有序，或者是数组中有重复数字，比如[]int{1,1,2,3,4,4}，求目标数字4出现的第一个位置，这种比较简单，读者可以自己尝试解一下，下面重点说一下旋转数组。

假设按照升序排序的数组在预先未知的某个点上进行了旋转。例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] 。

请找出其中最小的元素。

示例 1：

示例 2：

确定是否满足二分法的使用条件：前面数组都是整体有序，现在变成局部有序了，target是求最小元素，满足二分条件

确定特定元素target的伪代码，这题target是唯一个满足小于后一个数的（未旋转作为特殊情况），在图中为nums[4] return nums[mid+1] } else if nums[mid] right = mid - 1 } else if nums[mid] > nums[right] { left = mid + 1 } }

代码如下

注意这里有一个特殊情况哦，如果数组没有经过旋转就是整体有序，比如[1,2,3,4,5]就是一个未经旋转的数组，直接返回nums[0]，所以在写算法题的时候一定要考虑到特殊情况，因为本文主要介绍二分法的使用，所以这里就略写了。

我一直认为真正弄懂了一个算法时，是能够把算法融入与生活去解决一些实际问题的，比如做实验把人分成俩组，还有下面这道题都是用二分法去解决日常生活的问题，大家可以看一下

留一道很有意思的趣味题： 有N件产品，他们的重量都是G，但是当中有一件是不合格的产品，他的重量是g，那么现在给你一个称，求你称最少的次数找出这个产品，相信很多人小时候都遇到过这个题吧，学完了二分法之后，可以考虑一下用二分怎么解。

附上俩道练习题供大家练习

744. 寻找比目标字母大的最小字母

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