二分算法（超详细）

快速排序

题目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

#include

using namespace std;

const int N =100010;

int q[N];

int n,m;

int main(){
    
    cin>>n>>m;
    
    for(int i=0;i<n;i++) scanf("%d",&q[i]);
    
    for(int i=0;i<m;i++){
        
        int x;
        cin>>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<<r<<endl; //这里输出l和r都可以，因为最终时刻l和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
50

算法思想：二分的主要思想是在一个区间内部去二分答案（边界），每次选择答案所在的区间进行处理（每次区间缩小一半），当区间长度为1的时候（左右相等的时候），就找到了答案。
整数划分需要注意边界问题：
书写模板时候一定不要写错，顺序就是先找左端点再找右端点。
//注意：
1.mid一定要写在while循环的里面，因为mid的值在while过程中是不断更新的。
2.找左端点时候更新方式：mid=l+r>>1; if(check) r=mid; else l=mid+1;
3.找右端点时候更新方式：mid=l+r+1>>1; if(check) l=mid; else r=mid-1;
即 r与l对应取值的对应关系记住。

题目2 浮点数二分-数的三次方根

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

输入格式
共一行，包含一个浮点数 n。

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

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

数据范围
−10000≤n≤10000
输入样例：
1000.00
输出样例：
10.000000

 #include

using namespace std;


int main(){
    
    double x;
    
    cin>>x;
    
    double l = -10000, r =10000;
    
    while( r-l > 1e-7){ //因为是浮点数二分，随意不存在边界问题，就不用+1或-1
        
        double mid =(l+r)/2;
        if(mid*mid*mid < x) l=mid;
        else r= mid;
    }
    
    printf("%.6f",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

算法思想：浮点数二分对比整数二分不需要判断边界的情况，所以更加简单。但是看似很简单的一道题，有很多细节需要注意。
注意：1.在判断r-l时数据范围必须要小于1e-6，因为最后编译器判断时是保留小数点后六位的，如果是1e-6可能导致小数点后第六位的数不同，不能Accepted
2.在第一步确定数的范围时，要设为-10000到+10000，而不能设为n。
3.在while进行判断的时候必须是右边界减去左边界，或者取绝对值也可以。