【优选算法】简单却又恶心的二分

���录

题目链接：在排序数组中查找元素的第一个和最后一个位置

解析

左边第一个

右边第一个

重点细节

由题目总结出来的模板

参考答案

---

题目链接：在排序数组中查找元素的第一个和最后一个位置

二分算法虽然是logN的算法，但是在很多人眼中却不值一提，觉得它简单而且只能应用在有序数组中，但是自己写的时候却经常***循环，并且有的题在不是有序的时候也是可以使用二分的，本篇将以此题为例带你写出永无bug的二分算法。

对于最基本的二分法和二分的时间复杂度就不赘述了

解析

左边第一个

我们首先以上图为例，为了找到左边第一个数字，可以将数组分为两个部分——一部分小于t，一部分大于等于t

为了防止溢出，先将mid写成mid=left+（right-left）/2，（区间长度）这里视左右情况会有一点变化，而不是mid=（right+left）/2（会有溢出风险）

当mid落到左区间的时候，mid左边包括mid都不是所要的，所以left=mid+1，在新的区间[left,right]中继续寻找

当mid落到右区间的时候，可能此时mid的值已经是3了，但是不能返回，因为要找的是最左边的一个3。那么right=mid-1吗？当mid为最左边的那个3的时候，你会发现这样写就会跳过了要的答案，为了防止这种情况，right应该写成right=mid；

右边第一个

为了找到最右边的第一个数字，我们举一反三，继续将数组分为两个情况

 将数组分为小于等于t和大于t的部分

当mid落到左区间的时候，可能mid值等于target但是我们要找到的是最右边的target

和上面一样，为了防止mid此时是最右边的target，但是写成left=mid+1错过正确答案，所以left应该写成left=mid

当mid落到右区间的时候，该区间值都是大于target的，没有我们所需要的，所以right=mid-1

但是这里的mid应该写成mid=left+（right-left+1）/2

理由：如果没有+1的话，如果出现上面这种情况，mid永远都是指向第一个，left=mid，left也一直是第一个，left永远无法等于right，造成***循环

重点细节

细节问题

1.循环结束的条件

这里应该写成while(left