二分
简介
二分查找(binary search)，也称折半搜索(half-interval search)，对数搜索(logarithmic search)，是用来在一个有序数组中查找某一元素的算法。
时间复杂度O(log n)
工作原理
在一个有序数组中，每次考察中间的元素(\(\frac{l+r}{2}\))，根据当前元素是否满足题目要求，输出当前元素，在左半边区间查找或在右半边区间查找(三选一）。
在有序数组中查找目标元素
参考代码
// 有序数组为a[n]
// a[n]的元素个数为n
// 目标值为tar
// 假设目标值在数组中最多出现一次
int find(int tar){
int l=0;//左界
int r=n-1;//右界
while(l<=r){
int mid=(r-l)/2+l;//防止l+r的结果出界
if(a[mid]==tar)return mid;//找到目标值
if(a[mid]细节处理
-
判断条件
若判断条件改为l+1
下一步将变为
此时直接跳出循环，容易发现有数据没有判断，当然也可以在返回时特判一下。
若判断条件改为ll!=r，即l与r重叠时跳出循环。
下一步两个指针重叠并跳出循环，容易发现两个指针指向的数据未检验。 -
转移方式
若将l=mid+1改为l=mid，此时若两个指针相邻将陷入死循环(当数组中无目标数据时)。
若将r=mid-1改为r=mid，此时若两个指针重叠将陷入死循环(当数组中无目标数据时)。
这是因为l与r都是整数，当l+r为奇数时除于2结果将截断。
求解满足条件的最大(小)值
以最大值为例
一般情况下，由于数组是单调的，某个元素满足条件时，其左(右)边的所有元素都应该满足条件。
参考代码
int find(int tar){
int l=0;//左界
int r=n-1;//右界
while(l细节处理
-
判断条件
为啥这个时候的判断条件变成ll!=r而不是l<=r呢？
我们看下当l==r时，由于l指向的元素必满足条件，检验mid时范围不发生变化，又将陷入死循环。 -
转移方式
l=mid好理解，因为返回的是l指向的元素，所以l指向的元素在每一刻都要满足条件。但这时l与r相邻时不会陷入死循环吗？
mid=(r-l+1)/2+l当r+l为奇数时，此时mid的0.5将会进1，所以不会陷入死循环。
r=mid-1，首先为了避免死循环必须这样写，其次因为mid已经不满足条件了，可以踢出搜索范围了。
总结
二分的细节主要有两个。
1.判断条件(防止有数据没检验就跳出循环)
2.转移方式(避免死循环)