c/c++

lower_bound和upper_bound函数应用

Posted by Chenyawei on 2019-12-05
Words 1.2k and Reading Time 5 Minutes
Viewed Times

二分查找的应用 lower_bound( )和upper_bound( )

  • 使用时需要引用c++标准库中

在从小到大的排序数组中:

  • lower_bound( begin,end,num)：从数组的begin位置到end-1位置二分查找第一个大于或等于num的数字,找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。
  • upper_bound( begin,end,num)：从数组的begin位置到end-1位置二分查找第一个大于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

在从大到小的排序数组中:

  • lower_bound( begin,end,num,greater() ):从数组的begin位置到end-1位置二分查找第一个小于或等于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。
  • upper_bound( begin,end,num,greater() ):从数组的begin位置到end-1位置二分查找第一个小于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

实例：

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
#include <cstdio>
#include <algorithm>
#include <iostream>
using namespace std;

const int maxn=100000+10;
const int INF=2*int(1e9)+10;
#define LL long long
int cmd(int a,int b){
	return a>b;
}
int main(){
	int num[6]={1,2,4,7,15,34}; 
	sort(num,num+6);                           //按从小到大排序 
	int pos1=lower_bound(num,num+6,7)-num;    //返回数组中第一个大于或等于被查数的值 
	int pos2=upper_bound(num,num+6,7)-num;    //返回数组中第一个大于被查数的值
	cout<<pos1<<" "<<num[pos1]<<endl;
	cout<<pos2<<" "<<num[pos2]<<endl;
	sort(num,num+6,cmd);                      //按从大到小排序
	int pos3=lower_bound(num,num+6,7,greater<int>())-num;  //返回数组中第一个小于或等于被查数的值 
	int pos4=upper_bound(num,num+6,7,greater<int>())-num;  //返回数组中第一个小于被查数的值 
	cout<<pos3<<" "<<num[pos3]<<endl;
	cout<<pos4<<" "<<num[pos4]<<endl;
	return 0;	

}

运行结果：
3 7
4 15
2 7
3 4
  • lower_bound和upper_bound的代码，
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
int lower_bound(int A[], int left, int right, int cmpX)
{
    int mid;
    while (left < right)
    {
       mid = (left + right) / 2;
        if (A[mid] >= cmpX)
        {
            right = mid;
        }
        else
		{
			left = mid + 1;
		}   
    }
    return left;
}

int upper_bound(int A[], int left, int right, int cmpX)
{
    int mid;
    while (left < right)
    {
       mid = (left + right) / 2;
        if (A[mid] > cmpX)
        {
            right = mid;
        }
        else
		{
			left = mid + 1;
		}   
    }
    return left;
}
  • 可以作为解决“寻找有序序列第一个满足某一条件的元素的位置”问题的固定模版。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
二分区间[left,right]为左闭右闭，初值要必须覆盖

int solve(int left, int right){
    int mid;
    while(left < right){
        mid = (left + right) / 2;
        if(条件成立){
            right = mid;
        }else{
            left = mid + 1;
        }
    }
    return left;
}

例子：

给定一个正整数数列，和正整数 p，设这个数列中的最大值是 M，最小值是 m，如果 M≤m**p，则称这个数列是完美数列。

现在给定参数 p 和一些正整数，请你从中选择尽可能多的数构成一个完美数列。

输入格式：

输入第一行给出两个正整数 N 和 p，其中 N（≤105）是输入的正整数的个数，p（≤109）是给定的参数。第二行给出 N 个正整数，每个数不超过 109。

输出格式：

在一行中输出最多可以选择多少个数可以用它们组成一个完美数列。

输入样例：

1
2
10 8
2 3 20 4 5 1 6 7 8 9

输出样例：

1
8

代码实现：

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
51
52
53
54
#include <cstdio>
#include <algorithm>

using namespace std;

const int maxn = 100010;
int n,p,num[maxn];
bool cmp(int a,int b){
    return a < b;
}

int binarySearch(int i, long long x){
    if(num[n - 1] <= x) return n;
    int l = i + 1, r = n - 1, mid;
    while(l < r){
        mid = (l + r) / 2;
        if(num[mid] <= x){
            l = mid + 1;
        }else{
            r = mid;
        }
    }
    return l;
}

// int main(){
//     scanf("%d %d",&n,&p);
//     for(int i = 0; i < n; i++){
//         scanf("%d",&num[i]);
//     }
//     sort(num,num + n,cmp);
//     int ans = 1;
//     for(int i = 0; i < n; i++){
//         int j = binarySearch(i,(long long)num[i]*p);
//         ans = max(ans,j - i);
//     }
//     printf("%d\n",ans);
//     return 0;
// }

int main(){
    scanf("%d%d",&n,&p);
    for(int i = 0; i < n; i++){
        scanf("%d",&num[i]);
    }
    sort(num, num + n);
    int ans = 1;
    for(int i = 0; i < n; i++){
        int j = upper_bound(num + i + 1, num + n, (long long)num[i]*p) - num;
        ans = max(ans, j - i);
    }
    printf("%d\n",ans);
    return 0;
}
notice

欢迎访问 chenyawei 的博客, 若有问题或者有好的建议欢迎留言，笔者看到之后会及时回复。 评论点赞需要github账号登录，如果没有账号的话请点击 github 注册， 谢谢 !

If you like this blog or find it useful for you, you are welcome to comment on it. You are also welcome to share this blog, so that more people can participate in it. If the images used in the blog infringe your copyright, please contact the author to delete them. Thank you !

FEATURED TAGS
c/c++
FRIENDS