【3.整数与浮点数二分】

1.整数二分

二分本质

• 有单调性，一定可以二分
• 二分的题目，不一定非要有单调性

思路:分俩种情况,有俩种模板

具体考虑用哪一个模板：

• 碰到二分题，写完mid 之后，先写check函数
• 根据check(mid)想一下，true 和false该怎么更新区间
• 如果更新区间是 l = mid ,r = mid + 1 ,此时使用mid = (l + r + 1) / 2
• 如果更新区间是 r = mid, l = mid + 1, 此时使用mid = (l + r) / 2

如果在第一种情况下，l = r - 1,因为是除法是向下取整，所以mid = l ,此时更新区间还是[ l , r]死循环。

题目

给定一个按照升序排列的长度为 n 的整数数组，以及 q个查询。

对于每个查询，返回一个元素 k 的起始位置和终止位置（位置从 0 开始计数）。

如果数组中不存在该元素，则返回 -1 -1。
<br/>
输入格式
第一行包含整数 n 和 q，表示数组长度和询问个数。

第二行包含 n 个整数（均在 1∼10000 范围内），表示完整数组。

接下来 q 行，每行包含一个整数 k，表示一个询问元素。
<br/>
输出格式
共 q 行，每行包含两个整数，表示所求元素的起始位置和终止位置。

如果数组中不存在该元素，则返回 -1 -1。
<br/>
数据范围
1 ≤ n ≤ 100000
1 ≤ q ≤ 10000
1 ≤ k ≤ 10000
<br/>
输入样例：

6 3
1 2 2 3 3 4
3
4
5

输出样例

3 4
5 5
-1 -1

代码

# include <iostream>
const int N = 1e6 + 10;
using namespace std;
int n, m;
int q[N];

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i ++) scanf("%d", &q[i]);
  
    while (m --)
    {
        int x;
        scanf("%d", &x);
       
        int l = 0, r = n - 1;
       
        while(l < r)
        {
           int mid = (l + r) >> 1;
           if (q[mid] >= x) r = mid;
           else l = mid + 1;
         
        }
        if (q[l] != x) cout << "-1 -1"<< endl;
        else 
       {
           cout << l << " ";
           int l = 0, r = n - 1;
           while (l < r)
           {
               int mid = (l + r + 1) >> 1;
               if (q[mid] <= x) l = mid;
               else r = mid - 1;
           }
           cout << l << endl;
       }
   }
   return 0;
}

2.浮点数二分

• 浮点数二分，每次都会严格缩小一半，不用处理边界问题
• 而整数二分，因为有整数的存在，所以缩小不一定是一半，需要处理边界问题

思路：

• 与整数二分一样，只不过当r - l <= 1e6(非常小的数)，此时就不需要进行二分了

代码

求根号X的值

#include <iostream>
using namespace std;

int main()
{
    double x;
    cin >> x;
    
    double l = 0, r = x;
    while (r- l > 1e-8)
    {
        double mid = (l + r) / 2;
        
        if (mid * mid >= x) r = mid;
        else l = mid;
    }
    printf("%lf", l);
    return 0;
}

3.附加模板

整数二分

bool check(double x){/* */}       //检查x是否满足某种性质
//区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用；
int bsearch_1(int l, int r)
{
   while (l < r)
   {
       int mid = l + r >> 1;
       if(check(mid)) r = mid;  //check()判断mid是否满足性质
       else l = mid + 1;
   }
   return l;
}



//区间[l, r]被划分成[l, mid - 1]和[mid , r]时使用；
int bsearch_2(int l, int r)
{
   while (l < r)
   {
       int mid = l + r + 1 >> 1;
       if(check(mid)) l = mid;  //check()判断mid是否满足性质
       else r = mid - 1;
   }
   return l;
}

浮点数模板

bool check(double x){/* */}       //检查x是否满足某种性质
double bsearch_3(double l, double r)
{
   while (l < r)
   {
       double mid = l + r >> 1;
       if(check(mid)) l = mid;  //check()判断mid是否满足性质
       else r = mid ;
   }
   return l;
}