复兴无基础第二十二课 二分查找
2025-10-31 12:57:23
发布于：上海
3阅读
0回复
0点赞
T1查找x
#include <iostream>
using namespace std;
int a[110];
int main() {
int n, x;
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
cin >> x;
int l = 1, r = n;
while (l <= r) {
int mid = (l + r) / 2;
if (a[mid] == x){
cout << mid;
return 0;
} else if (a[mid] > x) r = mid - 1;
else l = mid + 1;
}
cout << -1;
return 0;
}
T2第一个大于等于x的数
#include <iostream>
using namespace std;
int a[110];
int main() {
int n, x, ans = -1;
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
cin >> x;
int l = 1, r = n;
while (l <= r) {
int mid = (l + r) / 2;
if (a[mid] >= x) {
r = mid - 1;
ans = mid;
} else {
l = mid + 1;
}
}
cout << ans;
return 0;
}
T3第一个大于x的数
#include <iostream>
using namespace std;
int main() {
int n, x, ans = -1;
int a[109];
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
cin >> x;
int l = 1, r = n;
while (l <= r) {
int mid = (l + r) >> 1;
if (a[mid] > x) {
r = mid - 1;
ans = mid;
}
else {
l = mid + 1;
}
}
cout << ans;
return 0;
}
T4【二分查找】lower_bound函数
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int n;
int a[109];
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
int x;
cin >> x;
cout << lower_bound(a + 1, a + 1 + n, x) - a;
return 0;
}
T5【二分查找】upper_bound函数
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int n;
int a[109];
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
int x;
cin >> x;
cout << upper_bound(a + 1, a + 1 + n, x) - a;
return 0;
}
T6【二分查找】最后一个小于等于x
#include <iostream>
using namespace std;
int main() {
int n, x, ans = -1;
int a[109];
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
cin >> x;
int l = 1, r = n;
while (l <= r) {
int mid = (l + r) >> 1;
if (a[mid] <= x) {
l = mid + 1;
ans = mid;
}
else {
r = mid - 1;
}
}
cout << ans;
return 0;
}
T7数的个数
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 1e5 + 9;
int n , m , a[maxn] , x;
int main()
{
//1、定义变量n,m,数组,进行输入
cin >> n;
for(int i = 1; i <= n; i++)
cin >> a[i];
//2、排序，保证二分的前提条件
sort(a + 1 , a + n + 1);
//3、m次询问
cin >> m;
while(m--)
{
//3.1、输入查询的数x
cin >> x;
//3.2、分别求出第一次大于等于的位置po 1，第一次大于的位置pos2
int pos2 = upper_bound(a + 1 , a + n + 1 , x) - a;
int pos1 = lower_bound(a + 1 , a + n + 1 , x) - a;
//3.3、x的个数为两者的差值
cout << pos2 - pos1 << endl;
}
return 0;
}
T8A-B 数对
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 2e5 + 9;
int n , c , a[maxn] , sum; //a-c=b
int main()
{
//1、定义变量n,c,数组,进行输入
cin >> n >> c;
for(int i = 1; i <= n; i++)
cin >> a[i];
//2、排序，保证二分的前提条件
sort(a + 1 , a + n + 1);
//2、枚举数字a
for(int i = 1; i <= n; i++)
{
//2.1、根据等式A-C=B,得出B
int b = a[i] - c;
//2.2、根据二分求数组中b的个数
int pos2 = upper_bound(a + 1 , a + n + 1 , b) - a;
int pos1 = lower_bound(a + 1 , a + n + 1 , b) - a;
//2.3、累加答案
sum += pos2 -pos1;
}
cout << sum;
return 0;
}
这里空空如也
有帮助，赞一个