二分算法¶

前言¶

配套视频：

新版本： www.bilibili.com/video/BV1jP4y1E7K5

旧版本： www.bilibili.com/video/BV1T44y1q7nL

一、二分简介¶

二分搜索是一种时间复杂为\(log_2n\)的算法，可以用于单调函数求根和单调序列查询的有效算法，即使在数列长度在很大的情况下也能很快对其查询，在此同时二分算法也是一种思维方式，在很多解题过程中可以更好的优化代码等等

二、二分算法的原理¶

每次拿目标数值（以下用key表示）与数组中间位置的数据（以下用a[mid]表示，mid表示数组中间位置索引值）进行比较，如果key大于a[mid]，继续将key与大于a[mid]部分的中间位置的值进行比较；如果key小于a[mid]，继续将key与小于a[mid]部分的中间位置值进行比较。

注：对于无序数组，若先进行排序，再使用二分查找，这种方法虽然可以实现查找，但是会改变最原始数组的元素位置，所以针对无序数组，最好用基本的查找算法实现

三、二分应用¶

二分算法通常是作为一种优化手段，帮助我们在维护一些单调类型的数据的时候能快速找到并修改，但是不是说二分算法一定依赖于数据单调性，我们深入的去想，其实二分算法只需要满足一个条件，当我们经过这个点后事情已经发生了，换句话说这个点对以后的状态造成了影响，没经过这个点的时候事情还没发生，那么对于这个点，对于这个点我们只需要用一个check()函数来作为抉择就好了。不会存在一些模板的二分题目给你做（比赛的时候）

四、二分代码实现¶

4.1 朴素实现¶

int search(int l,int r,int key) {
    int mid = l + r >> 1;
    while(a[mid] != key) {
        if(a[mid] > key) {
            r = mid - 1;
        }
        else {
            l = mid + 1;
        }
        if(l > r) return -1; //没找到
        mid = l + r >> 1;
    }
    return mid;
}

4.2 通用实现¶

int search(int k) {
    int l = -1,r = n;//注意的是数组是从0开始的
    while(l + 1 < r) {
        int mid = l + r >> 1;
        if(a[mid] <= k)
            l = mid;
        else 
            r = mid;
    }
    return r;//返回的是大于k的第一个位置
}