二分查找 编译错误如何解决

Question

我哪里错了（编译错误）
请在一个有序不递减的数组中（数组中的值有相等的值），采用二分查找，找到最后1次出现值x的位置，如果不存在x请输出-1。

请注意：本题要求找出q个x，每个x在数组中最后一次出现的位置。

比如有6个数，分别是：1 2 2 2 3 3，那么如果要求3个数：3 2 5，在数组中最后一次出现的位置，答案是：6 4 -1。

#include<cstdio>
using namespace std;
int main() {
    int n;
    scanf("%d",&n);
    int a[100005];
    for(int i=0;i<=n;i++){
        scanf("%d",&a[i]);
    }
    
    int x;
    scanf("%d",&x);
    int b[100005];
    for(int i=0;i<=x;i++){
        scanf("%d",&b[i]);
    }
    int l=0,r=n-1,mid
    for(int i=1;i<=x;i++){
        while(l<=r){
            int mid=(l+r)/2;
            if(a[mid]==x){
                while(a[mid+1]==x){
                    mid++;
                }
                printf("%d",mid);
            }
            else if(a[mid]<b[i]){
                l=mid+1;
            }
            else if(a[mid]>b[i]){
                r=mid-1;
            }
        }
        if(l>r){
            printf("-1");
        }
    }
    return 0;
}

比如有6个数，分别是：1 2 2 2 3 3，那么如果要求3个数：3 2 5，在数组中最后一次出现的位置，答案是：6 4 -1。

Answer 1

以下内容由CHATGPT及阿里嘎多学长共同生成、有用望采纳：

---

你的代码中有几个问题需要解决，我将逐一指出并提供修改建议：

1. 数组定义问题：

   • 你的数组定义为 int a[100005]; 和 int b[100005];，但实际使用时超出了数组的索引范围。数组索引从0开始，因此最大索引应该是 n-1 和 x-1。

2. 数组输入问题：

   • 在输入数组 a 时，循环条件应该是 i < n 而不是 i <= n。

3. 数组 b 的使用问题：

   • 你试图在数组 b 中存储查询的值，但代码中并没有正确使用它。你需要将查询值存储在 b 中，并在二分查找时使用它们。

4. 二分查找逻辑问题：

   • 你的二分查找逻辑中，变量 x 被错误地用作查询值，而实际上它应该是数组 b 中的元素。

5. 输出格式问题：

   • 输出时没有添加分隔符，且在每次输出后没有添加换行符。

6. 编译错误：

   • 代码中存在一个未完成的语句 int l=0,r=n-1,mid，这会导致编译错误。

以下是修改后的代码：

#include <cstdio>
using namespace std;

int main() {
    int n;
    scanf("%d", &n);
    int a[100005];
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }

    int q;
    scanf("%d", &q);
    int b[100005];
    for (int i = 0; i < q; i++) {
        scanf("%d", &b[i]);
    }

    for (int i = 0; i < q; i++) {
        int x = b[i];
        int l = 0, r = n - 1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (a[mid] == x) {
                while (mid < n - 1 && a[mid + 1] == x) {
                    mid++;
                }
                printf("%d ", mid + 1); // 数组索引从0开始，因此输出时加1
                break;
            } else if (a[mid] < x) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        if (l > r) {
            printf("-1 ");
        }
    }
    return 0;
}

解释：

• 我将数组 b 用于存储查询的值，并将查询值 x 从数组 b 中读取。
• 在二分查找中，我检查 a[mid] == x 并继续向右查找直到 a[mid + 1] != x，这样就能确保找到最后一个出现的 x。
• 输出时，我添加了空格作为分隔符，并在每次输出后添加了空格，以便更清晰地显示结果。

这样修改后的代码应该能够正确编译并运行，满足题目要求。