三个WA
原题链接：8022.查找
2024-10-05 13:42:09
发布于：江西
12阅读
0回复
0点赞
#include<bits/stdc++.h>
using namespace std;
int n,m,a[1000005],b[1000005];
int find(int number)
{
int l=0,r=n+1;
while(l+1!=r)
{
int mid=l+(r-l)/2;
if(a[mid]==number&&a[mid-1]!=number) return mid;
else if(a[mid]>number) r=mid;
else l=mid;
}
return -1;
}
int main()
{
scanf("%d %d", &n, &m);
for(int i=1;i<=n;i++)
scanf("%d", &a[i]);
for(int i=1;i<=m;i++)
scanf("%d", &b[i]);
for(int i=1;i<=m;i++)
printf("%d ", find(b[i]));
}
全部评论 2
改了下你个find函数
int find(int number) { int l=1,r=n; while(l<=r) { int mid=l+(r-l)/2; if(a[mid]>=number) r=mid-1; else l=mid+1; } return (a[l]!=number?-1:l); }1周前 来自 广东
0
对于你提供的代码，有一些细节需要调整以确保能正确处理查找问题并避免边界条件错误。以下是分析以及改进代码的建议：
问题分析：
- 边界条件问题：当前代码的
find函数在查找过程中，如果a[mid] == number，你会检查a[mid-1] != number来确认是否为第一次出现的编号，但这里可能会访问越界位置（即a[0]）。 - 二分查找逻辑不完全正确：需要确保在查找到目标值后，通过二分查找锁定其第一次出现的位置，而不是简单地直接返回。
- 使用合适的 IO 方式：由于输入输出数据量较大，建议使用
scanf和printf来提高速度，虽然你已经在使用这些函数，但我将继续保留这些部分。
改进代码：
#include <bits/stdc++.h> using namespace std; int n, m; int a[1000005]; int b[1000005]; // 查找 number 在数组 a 中第一次出现的位置，返回下标(从1开始)，若不存在返回 -1 int find_first_occurrence(int number) { int l = 1, r = n + 1; // 左边界设为1，右边界为 n+1 while (l < r) { // 标准二分查找 int mid = l + (r - l) / 2; if (a[mid] >= number) r = mid; // 向左收缩 else l = mid + 1; // 向右收缩 } // 判断最终找到的位置是否是目标值且是否为第一次出现的位置 if (l <= n && a[l] == number) return l; else return -1; } int main() { // 快速输入 scanf("%d %d", &n, &m); for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); } for (int i = 1; i <= m; i++) { scanf("%d", &b[i]); } // 处理每次询问 for (int i = 1; i <= m; i++) { printf("%d ", find_first_occurrence(b[i])); } printf("\n"); return 0; }改进点说明：
- 修正边界条件：使用
l = 1和r = n + 1来确保下标访问不会越界，二分查找时不会访问a[0]或其他无效位置。 - 二分查找锁定第一次出现的位置：修改了二分查找的逻辑，通过
r = mid确保查找过程中能锁定最左边的目标值下标。 - 快速 IO：保留了
scanf和printf来处理大量数据输入输出。
测试样例：
输入：
11 3 1 3 3 3 5 7 9 11 13 15 15 1 3 6输出：
1 2 -1总结：
改进后的代码修正了查找函数的边界问题和查找逻辑，能够正确处理大规模的输入输出。如果还有其他问题或测试案例需要调整，请告诉我！
1周前 来自 浙江
0- 边界条件问题：当前代码的
有帮助，赞一个