二分查找

二分算法解析

二分的判断条件通常是通过列出有关要二分的量和其他变量之间的关系方程：

1. 暴力解法要循环所有可能的边长值
2. 通过二分来一步步得缩小查找的区间
3. 二分的核心就是通过某些性质使得可以缩小查找区间来减少时间复杂度

二分步骤：

1. 先写一个check函数(判断条件要具有二段性，并且答案一定是二段性的分界点)
2. 判定在check的情况下（true和false的情况下），如何更新区间。
3. 在check(m) == true的分支下是:
   • l = mid的情况，中间点的更新方式是m = (l+r+1)/2
   • r = mid的情况，中间点的更新方式是m = (l+r)/2

这种方法保证了：

1. 最后的 l == r
2. 搜索到达的答案是闭区间的，即 a[l] 是满足check()条件的。

二分模板
模板1就是在满足chek()的区间内找到左边界，模板2在满足check()的区间内找到右边界。然后无论是左边界还是右边界，都应该是整个区间中某一段满足某性质（如单调不降）与另一段不满足该性质的分界点

口诀：左加右减

//查找左边界 SearchLeft 简写SL
int SL(int l, int r)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid; 
        else l = mid + 1; 
    }   
    return l;
}

//查找右边界 SearchRight 简写SR 
int SR(int l, int r) 
{
    while (l < r)
    {                   
        int mid = l + r + 1 >> 1; //需要+1 防止死循环
        if (check(mid)) l = mid;
        else r = mid - 1; 
    }
    return r; 
}

浮点数二分

1. 浮点数二分不需要判断边界
2. 题目要求保留6位小数的时候，就要求l和r的差值小于10的负8次方比较保险

   #include <stdio.h>
   
   // 浮点数二分
   int main(){
       double n;
       scanf("%lf",&n);
       double l=-10000,r=10000;
       //保留6位小数的时候，就要求l和r的差值小于10的负8次方比较保险
       while(r-l>1e-8){
           double mid = (l+r) / 2;
           if(mid*mid*mid >= n){
               r = mid;
           }
           else{
               l = mid;
           }
       }
       printf("%.6lf",l);
       return 0;
   }

STL中的有关二分的函数

tip:这些关于二分的stl函数，都只会查找指定元素后面的值，所以要在排好序的数组中进行查找

1. binary_search()函数，作用：对一个不降序列进行二分查找，如果所查找的值在序列中出现了，返回true，没有出现，返回false。

int a[5] = {1,3,5,5,8};
bool flag = binary_search(a,a+5,3); //返回的是布尔值
cout << flag;

2. lower_bound()函数，作用：对一个不降序列进行二分查找，返回第一个大于等于所查找的值的元素下标，注意返回的是指针变量！！！ 如果所有元素都小于val，则返回last的位置，且last的位置是越界的

3. upper_bound()函数，作用：对一个不降序列进行二分查找，返回第一个大于所查找的值的元素下标，注意返回的是指针变量！！！

   int a[5] = {2,3,2,1,8};
   auto pos = upper_bound(a,a+5,3); //返回的是指针变量
   auto index =  pos-a; //对应元素下标(从0开始)
   cout << index << endl << *pos << endl << a[index];

4. 如果查找第一个小于某个元素的下标，则加上greater<int>()

例题：数的范围

给定一个按照升序排列的长度为 n 的整数数组，以及 q 个查询。对于每个查询，返回一个元素 k 的起始位置和终止位置（位置从 0 开始计数）。
如果数组中不存在该元素，则返回 -1 -1。

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1e5 + 10;

int n,q;
int l,r;
int a[N],b[N];

int main(){
    cin >> n >> q;
    for(int i =0;i<n;i++){
        cin >> a[i];
    }
    while(q--){
        int k;
        cin >> k;
        if(!binary_search(a,a+n,k)){
            cout << "-1" << " " << "-1" << endl;
            continue;
        }
        int l = lower_bound(a,a+n,k) - a;
        int r = upper_bound(a,a+n,k) - a;
        cout << l << " " << r-1 << endl;
    }
    return 0;
}