在算法中用的比较多的查找算法是二分查找，在这里梳理一下整数二分和浮点数二分的思路。

将来复习数据结构的话也会在这里补充。

二分查找

（一）是什么

二分查找（折半查找：Binary Search）的查找过程：先确定待查记录所在的范围（区间），然后逐步缩小范围直到找到或找不到该记录为止。

注：

就算是找不到这个记录最终也是可以停下的，只不过停下的位置对应的值并不是想要的。

（二）优势

时间复杂度低：O(logn)

推导：

数据大小为n，每次查找后数据都会减半，最坏情况为直到区间数为1个时才停止，即：n * (1/2)的x次方 = 1

解得x = logn

（三）两个板子算法

首先必须清楚一件事，二分算法解决的本质是：寻找某一性质的边界，给出的两个板子就是找到性质1的右边界（箭头1）和性质2的左边界（箭头2）。

1.确定性质1的边界——找箭头1

mid = l + r + 1 >> 1

if(check(mid)): //判断是否满足该性质

Ture

mid在箭头1的左边，那要找到箭头的话需要改变区间：l = mid，使[l, r] -> [mid, r] （包含mid，因为mid也满足性质。下同理）。

False

mid在箭头1的右边，需要：r = mid - 1， 使[l, r] -> [l, mid -1]

2.确定性质2的边界——找箭头2

mid = l + r >> 1

if(check(mid)): //判断是否满足该性质

Ture

r = mid, [l, r] -> [l, mid]

False

l = mid + 1, [l, r] -> [mid + 1, r]

板子如下：

注意： http://dxb.myzx.cn/

1.l = mid时mid后面需要+1

2.这两个板子的返回结果就是两个边界

3.图中的性质1和性质2往往对应的是小于和大于

bool check(int x){/* ... */}

int bsearch_1(int l, int r){

//性质1

while(l < r){

int mid = l + r + 1 >> 1;

if(check(mid)) l = mid;

else r = mid - 1;

}

return r; //此时l和r一样，返回谁都可以

}

int bsearch_2(int l, int r){

//性质2

while(l < r){

int mid = l + r >> 1;

if(check(mid)) r = mid;

else l = mid + 1

}

return l;

}

AcWing 789. 数的范围

这道题就是怎么用了。比如1 2 2 3 3 4问你3的起始位置和终止位置。（从0开始）

既然是有序的，那很轻易可以看出1 2 2 是<3的，4>3，我们可以将问题转化为寻找 <=3 右边界和 >=3 的左边界。

<=3 的右边界是位置4，>=3 的左边界是位置3， 很明显不是我们想要的答案。那我们直接颠倒顺序，寻找 >=3 的左边界 和 <=3 的右边界就可以解决问题。

如果寻找不到，那么边界位置的值一定不是寻找的值，一个if语句就可以解决。

#include<bits/stdc++.h>

using namespace std;

const int N = 100010;

int a[N];

int n, q;

int main(){

    scanf("%d%d", &n, &q);

    for(int i = 0; i < n; i ++) scanf("%d", &a[i]);

    while(q --){

        int k;

        scanf("%d", &k);

        //寻找k的左边界

        //>=k的左边界，满足性质2

        int l = 0, r = n - 1;

        while(l < r){

            int mid = (l + r) >> 1;

            if(a[mid] >= k) r = mid;

            else l = mid + 1;

        }

        if(a[l] != k) cout << "-1 -1"<<endl;

        else{

            printf("%d ", l);

            //寻找k的右边界

            //<=k的右边界，满足性质1

            l = 0, r = n - 1;

            while(l < r){

                int mid = (l + r + 1) >> 1;

                if(a[mid] <= k) l = mid; // l = mid 前面的mid应该+1

                else r = mid - 1;

            }

            printf("%d\n", r);

        }

    }

    return 0;

}

最常用的就是上面的整数二分板子了，浮点数二分更简单，没有+1-1的那些事儿。板子如下：

const double eps = 1e-6 ;一般定义的比题给的小两位

double bsearch_3(double l, double r){

while(r - l > eps){

double mid = l + r >> 1;

if(check(mid)) r = mid;  //结合题

else l = mid;

}

return l;

}

eg.求三次方根

#include<bits/stdc++.h>

using namespace std;

const double eps = 1e-8 ;//经验之谈，eps比题目要求的多两位

int main(){

    double n;

    scanf("%lf", &n);

    double l = -10000, r = 10000;

    while(r - l > eps){

        double mid = (r + l)/2;

        if(mid * mid * mid >= n) r = mid;

        else l = mid;

    }

    printf("%lf", l); //double类型输出默认是6位，符合题目要求

    return 0;

}

（四）哪些情况使用

这里谈论的就不仅仅是算法了，还有数据结构的一些东西。

存储的数据结构应该是可以实现随机访问的数组，而不是链表。（链表不支持随机访问）

数组内的数据必须有序

更适合处理静态数据（没有频繁的数据插入、删除操作）

太小的不适合，因为顺序查找就可以解决

太大的也不适合，因为二分底层依赖的就是数组，而数组在内存中就是一段连续的空间，你需要1G的空间，即使内存剩下2G可能也不够用，因为剩余的2G可能是离散分配后的结果，并没有1G的连续空间。

二分依赖的只有数组，所以大部分情况还是可以解决的。同时二分可以解决的散列表、二叉树也都可以解决。这些以后再补充，算法这里最常用的是二分。

————————————————

版权声明：本文为CSDN博主「御用厨师」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。

原文链接：https://blog.csdn.net/qq_45520647/article/details/119176850