8. 查找
1 题目描述
查找
| 成绩 | 10 | 开启时间 | 2021年09月24日 星期五 18:00 |
| 折扣 | 0.8 | 折扣时间 | 2021年11月15日 星期一 00:00 |
| 允许迟交 | 否 | 关闭时间 | 2021年11月23日 星期二 00:00 |
输入 n(n ≤ 10^6)个不超过 10^9的单调不减的（就是后面的数字不小于前面的数字）非负整数 ，然后进行 m(m ≤ 10^5) 次询问。
对于每次询问，给出一个整数 q(q ≤ 10^9)，要求输出这个数字在序列中第一次出现的编号，如果没有找到的话输出 -1 。
输入描述
第一行 2 个整数 n 和 m，表示数字个数和询问次数。
第二行 n 个整数，表示这些待查询的数字，有序
第三行 m 个整数，表示询问这些数字的编号，从 1 开始编号。
输出描述
m 个整数表示答案，注意换行。
接下来将由系统输出你的询问记录。
当你的答案正确且你询问的次数在( 2 * m * log(n) ) + 3次以内时，你将AC此题。此题log以2为底。
PS：部分超过时间限制的可多次提交，即可通过
预设代码
前置代码
/* PRESET CODE BEGIN - NEVER TOUCH CODE BELOW */ #include <bits/stdc++.h> int n, m, q, a[1000005]; int find(int x,int n);
int cmp(int i, int x)
{ if(i > n|| i <= 0) return -2; if (a[i] > x) return 1; if (a[i] == x) return 0; 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", &q); int ans = find(q,n); //看看查找的结果 printf("%d ", ans); //输出 } printf("\n"); return 0;
} // //请补充下列代码
// int find(int x,int n)
// { // } /* PRESET CODE END - NEVER TOUCH CODE ABOVE */
| 测试输入 | 期待的输出 | 时间限制 | 内存限制 | 额外进程 | |
|---|---|---|---|---|---|
| 测试用例 1 | 以文本方式显示
| 以文本方式显示
| 1秒 | 153600KB | 0 |
2 代码
#include <bits/stdc++.h> int n, m, q, a[1000005]; int find(int x,int n);
int cmp(int i, int x)
{ if(i > n|| i <= 0) return -2; if (a[i] > x) return 1; if (a[i] == x) return 0; return -1;
} int main()
{ freopen("file in.txt","r",stdin);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", &q); int ans = find(q,n); //看看查找的结果 printf("%d ", ans); //输出 } printf("\n"); return 0;
} // //请补充下列代码
//找x在a中第一次出现的编号
// int find(int x,int n)
// {
// int mid;
// int ans;
// int left,right;
// int flag=0;// left=1;right=n;
// mid=0;// //数字个数大于等于3个才会进入这个循环
// while(left<right-1){// /*if((right-left+1)%2==1){
// // 奇数
// mid = (right-left)/2+left;
// }
// else{
// mid = (right-left)/2+left;
// }*/
// //不用考虑奇偶性
// mid = (right-left)/2+left;
// // 比较中间这个数和x的大小
// ans = cmp(mid,x);
// if(ans==-2){
// exit;
// }
// else if(ans==1){
// // 这个数在左边
// right = mid;
// }
// else if(ans==-1){
// //这个数在右边
// left=mid;
// }
// else{
// // 找到了
// flag=1;
// break;
// }
// }
// //如果上面的循环没有找到,那么还剩下三个数没有找 left left+1 right
// // 或者说直接没有进入上面的while循环中
// if(flag==0){
// while(left<=right){
// ans = cmp(left,x);
// if(ans==0){
// //找到的话直接返回left的值并且退出这个函数了
// return left;
// }
// else{
// left++; // }
// }
// //如果循环走完了都没有退出这个函数，说明没有找到相等的数
// return -1;
// }// //如果是在while循环里面找到的就会运行下面的语句
// if(flag){
// //找到了这个数，但是还要验证他是不是第一次出现
// while(mid-1>=1){
// ans=cmp(mid-1,x);
// if(ans==0){
// //他的前一个数还是和他相等
// mid--;
// }
// else{
// //他的前一个数和x不相等，那么现在这个mid就是我们要找的第一次出现的x
// break;
// }
// }
// return mid;
// }
// else
// return -1;
// }// 再循环里面找到这个数的时候不要退出，继续循环二分法
// 如果前面有的话，最终会落在这个数上面，如果没有的话，最后left也会回到这个数，和right相等
int find(int x, int n){int left,right;int mid;int ans;int flag=0,temp;left=1;right=n;while(left<=right){// 没有必要区分奇偶，这里只需要让mid取中就行，并不是前面那种两个两个拿出来会有一个落单的情况mid=(right-left)/2+left;ans= cmp(mid,x);if(ans==-2){exit(0);}else if(ans==1){// mid这个数已经比较过了，不用在比较了，直接向前面推进一个数right = mid-1;}else if(ans==-1){left=mid+1;}else{right = mid-1;//不往前推的话这个就会进入死循环temp=mid;//把这个数记录下来，防止往前推以后没有这个数了flag=1;}}// 循环结束之后if(ans==0)return left;else if(flag==1)return temp;return -1;
}// 不用区分n的奇偶性
// mid比较过后应该跳过，简化了算法的复杂度