前言

蓝桥杯官网：蓝桥杯大赛——全国大学生TMT行业赛事
✨本博客讲解 蓝桥杯C/C++ 备赛所涉及算法知识，此博客为第三讲：二分【例题】

二分【习题】详见博客：蓝桥杯第三讲–二分【习题】

本篇博客所包含习题有：
👊数的范围
👊数的三次方根

博客内容以题代讲，通过讲解题目的做法来帮助读者快速理解算法内容，需要注意：学习算法不能光过脑，更要实践，请读者务必自己敲写一遍本博客相关代码！！！

二分

关于二分的模板，详细见博客：二分算法模板
二分的解题步骤如下：

1. 找一个区间 [L, R]，使得答案一定在该区间中
2. 找一个判断条件，使得该判断条件具有二段性，并且答案一定是该二段性的分界点
3. 分析终点 M 在该判断条件下是否成立，如果成立，考虑答案在哪个区间；如果不成立，考虑答案在哪个区间；
4. 【本点只对整数二分有关，浮点数的二分只需前三点】如果更新方式写的是 R = Mid，则不用做任何处理；如果更新方式写的是 L = Mid，则需要在计算 Mid 时加上1

数的范围

题目要求

题目描述：

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

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

如果数组中不存在该元素，则返回 -1 -1。

输入格式：

第一行包含整数 n 和 q，表示数组长度和询问个数。

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

接下来 q 行，每行包含一个整数 k，表示一个询问元素。

输出格式：

共 q 行，每行包含两个整数，表示所求元素的起始位置和终止位置。

如果数组中不存在该元素，则返回 -1 -1。

数据范围：

1 ≤ n ≤ 100000
1 ≤ q ≤ 10000
1 ≤ k ≤ 10000

输入样例：

6 3
1 2 2 3 3 4
3
4
5

输出样例：

3 4
5 5
-1 -1

思路分析

模板题，不做解释，强调一点，当输入数据的范围 大于 1e5 的时候，建议使用 scanf printf，不要使用 cin cout，因为蓝桥杯是 OI 赛制，不要因为这种错误扣分。

代码

#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 100010;

int q[N];
int n, m;

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i ++ ) 
        scanf("%d", &q[i]);
    
    while (m -- )
    {
        int k;
        scanf("%d", &k);
        
        int l = 0, r = n - 1;
        while (l < r)   //先找左端点,左端点是第一个等于k的点
        {
            int mid = l + r >> 1;
            if (q[mid] < k) l = mid + 1;
            else r = mid;
        }
        
        if (q[l] != k)
            puts("-1 -1");
        else 
        {
            printf("%d ", l);
            // 接下来找右端点
            r = n - 1;
            while (l < r)
            {
                int mid = l + r + 1 >> 1;
                if (q[mid] > k) r = mid - 1;
                else l = mid;
            }
            printf("%d\n", r);
        }
    }
    
    return 0;
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
 

数的三次方根

题目要求

题目描述：

给定一个浮点数 n，求它的三次方根。

输入格式：

共一行，包含一个浮点数 n。

输出格式：

共一行，包含一个浮点数，表示问题的解。

注意，结果保留 6 位小数。

数据范围：

−10000 ≤ n ≤ 10000

输入样例：

1000.00

输出样例：

10.000000

思路分析

模板题，不做解释，强调一点，本题要求保留 6 位小数，所以我们在二分的时候设置精度设置为 1e-8，即往后取2位精度，这个小细节很重要。

代码

#include <cstdio>
#include <algorithm>
#include <algorithm>

using namespace std;

int main()
{
    double n;
    scanf("%lf", &n);
    
    double l = -10000, r = 10000;
    while (r - l > 1e-8) //保留6位小数,精度往后取2位
    {
        double mid = (l + r) / 2;
        if (mid * mid * mid >= n) 
            r = mid;
        else l = mid;
    }
    
    printf("%lf", l);
    
    return 0;
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
 

文章来源: chen-ac.blog.csdn.net，作者：辰chen，版权归原作者所有，如需转载，请联系作者。

原文链接：chen-ac.blog.csdn.net/article/details/122578654