简介

二分查找(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]<tar)l=mid+1;//接下来在右半边查找
        else r=mid+1;//接下来在左半边查找
    }
    return -1;//没找到
}

细节处理

• 判断条件
  若判断条件改为l+1<r，即l与r不相邻。
  
  下一步将变为
  
  此时直接跳出循环，容易发现有数据没有判断，当然也可以在返回时特判一下。
  若判断条件改为l<r或l!=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<r){
        int mid=(r-l+1)/2+l;//防止l+r的结果出界
        if(check(mid))l=mid;//check()检验mid是否满足条件
        else r=mid-1;
    }
    return l;
}

细节处理

• 判断条件
  为啥这个时候的判断条件变成l<r即l!=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.转移方式(避免死循环)