题解(假正经)
2024-08-21 19:21:11
发布于:广东
17阅读
0回复
0点赞
废话
这道题目要求我们使用二分写法,所有我们不得不使用我们的大脑构件出二分。
相信很多小伙伴们做过用二分求x在a数组中的哪个位置,但是却不知道如何用二分去做求第一个大于x的数的下标,不过这也很简单,只需要使用你聪明智慧的大脑就可以轻松解决。
写题思路
由于用二分去求第一个大于x的数,所以我们需要想如何定义ans。主要思路:如果大于x,那么这个就有可能就是第一个大于x的数的下标,可是我们无法确定,不过我们先用ans保存(ans初始化为-1),记得赋值变量;而否则的话,我们就使用常规操作将进行赋值,直到退出while循环后,我们的ans要么是-1,要么是第一个大于x的数,因为我们是实时赋值给ans的,范围逐渐缩小就使ans等于第一个大于等于x的数的下标。
AC Code
#include<iostream>
using namespace std;
int a[105];
int main() {
int n, ans = -1;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
int x;
cin >> x;
int r = n; // 定义右边界 r 为数组的最后一个元素的索引
int l = 1; // 定义左边界 l 为数组的第一个元素的索引
int mid; // 定义中间值变量 mid,用于在二分查找中计算中间位置
// 二分查找循环
while (l <= r) {
mid = (r + l) / 2; // 计算中间索引
if (a[mid] > x) { // 如果中间元素大于 x
r = mid - 1; // 将右边界移动到中间位置的左侧
ans = mid; // 更新结果为当前大于x的数的下标
} else {
l = mid + 1; // 如果中间元素小于或等于 x,将左边界移动到中间位置的右侧
}
}
cout << ans;
return 0;
}
这里空空如也
有帮助,赞一个