二分法心得

原教程见labuladong

首先，我们建议左右区间全部用闭区间。那么第一个搜索区间：left=0; right=len-1;

进入while循环，结束条件是right<left。

然后求mid，如果nums[mid]的值比target大，说明target在左边，收缩搜索空间：right=mid-1。反之，target在右边，收缩搜索空间：left=mid+1。

注意计算mid时，不要用mid=(left+right)/2，这样可能溢出，要用mid=left+(right-left)/2。

以上是经典二分法查找。

---

但是如果要寻找左右边界呢？比如在排序数组中寻找某元素的左右边界。

这时外面的框架不变，还是闭区间，还是一样的循环结束条件。

但是里面的搜索条件变了。比如搜索左边界的话，我们的nums[mid]==target，这时我们需要往左收缩区间，也就是right=mid-1。其他两个条件不变，还是在寻找target。

所以他们最终会找不到target，最后一次是left=mid+1，也就是左边界的位置，返回left即可。

访问右边界是一样的原理。

这里注意，如果整个数组里就不存在target，target是一个很大的数，那么最终left=len，访问溢出了。所以要判断 left==len？。