#创作计划#XP02第二天学习笔记
2025-08-04 10:30:31
发布于：浙江
21阅读
0回复
0点赞
目录:
一.二分查找
二.二分上下界
一.二分查找:
二分查找概念:
二分查找是一种查找方式，时间复杂度为 O(logN) 。他可以高效率的查找到在一个有序序列里的一个元素
二分查找步骤:
1.确定左右端点:
int l = 左端点,r = 右端点;
2.开始循环查找步骤
while(l <= r){
//查找步骤(假代码)
}
3.确定中间值
mid = (l + r) / 2;
4.判断
if(a[mid] == m){ // 如果中间值就是要查找的值
cout << mid << endl;
break;
else if(a[mid] > m){
r = mid - 1 ;//如果中间值太大了就把右端点向左移到mid - 1
}else if(a[mid] < m){
l = mid + 1;//如果中间值太小了就把左端点
原因如下图:
总代码(Q次询问数组里面x的位置):
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5;
int a[N]
int main(){
int n,Q;
cin >> n >> Q;
for(int i = 1;i <= n;i++)cin >> a[i]；
while(Q--){
int x;
cin >> x;
int l = 1,r = n;//确定左右端点
while(l <= r){ //开始循环步骤
int mid = (l + r) / 2; //确定中间值
if(a[mid] == x){
cout << mid << endl;
break;
}else if(a[mid] > x)r = mid - 1;
else l = mid + 1;
}
}
}
二.二分上下界(其实就是lower_bound和upper_bound用法):
上下界定义:x的上界指的是数组中第一个大于x的元素，而下界就是数组中第一个大于等于x的元素
1.函数lower_bound():
定义:查找从开始地址到结束地址里第一个>=x的元素,如果没有返回值为比范围大的数字，不能查找结构体
用法:
lower_bound(开始地址，结束地址，查找元素);
lower_bound(a+1,a+n+1,x);//这里返回的是第一个 >= x的存储地址
lower_bound(a+1,a+n+1,x)-a;//这里返回的是第一个 >= x在a里面的下标
if(lower_bound(a,a+n,x)-a > n);//判断是否有 >= x 的数
**
函数upper_bound():
定义：查找从开始到结束地址里第一个 > x的元素，如果没有返回值就为比范围大的数字，不能查找结构体
用法:
upper_bound(开始地址，结束地址，查找元素);
upper_bound(a+1,a+n+1,x);//这里返回的是第一个 > x的存储地址
upper_bound(a+1,a+n+1,x)-a;//这里返回的是第一个 > x在a里面的下标
if(upper_bound(a,a+n,x)-a > n);//判断是否有 > x 的数
结合：
1.计算非降序序列a的里面有几个x
int left,right;//定义上下界变量
left = lower_bound(a+1,a+n+1,x)-a;//给下界变量赋值
right = upper_bound(a+1,a+n+1,x)-a;//给上界变量赋值
int num = right - left; // 有几个x
简便写法:
int num = upper_bound(a+1,a+n+1,x) - lower_bound(a+1,a+n+1,x);//这里不用-a是因为两个地址相减
有帮助，赞一个