有 $n$ 个数($n \le 1000000$),这 $n$ 个数已按从大到小顺序存放在一个数组中,然后有 $T$ 次查询,每次输入一个数,要求用折半查找法找出该数在数组中第一次出现的位置。如果不在数组中输出 0。
时间: 2023-12-31 19:04:13 浏览: 25
好的,我知道了。这个问题可以用二分查找来解决。
具体做法是,首先找到数组的中间位置,将要查询的数与中间位置的数比较。如果相等,则直接返回当前位置。如果要查询的数比中间位置的数小,则在左半部分继续查找;如果比中间位置的数大,则在右半部分继续查找。每次递归查找时,需要更新查找范围(左右边界),直到找到要查询的数或者确定其不存在于数组中为止。
以下是代码实现:
```
#include <iostream>
#include <cstdio>
using namespace std;
int binary_search(int a[], int l, int r, int x)
{
int mid;
while (l <= r) {
mid = (l + r) / 2;
if (a[mid] == x) return mid;
if (a[mid] > x) r = mid - 1;
else l = mid + 1;
}
return 0;
}
int main()
{
int n, t, a[1000001];
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
scanf("%d", &a[i]);
}
scanf("%d", &t);
while (t--) {
int x;
scanf("%d", &x);
printf("%d\n", binary_search(a, 1, n, x));
}
return 0;
}
```