php自己做网站,贵阳网站设计方案,画册设计排版的技巧和规则,wordpress手动加水印Description
给出一个队列和要查找的数值#xff0c;找出数值在队列中的位置#xff0c;队列位置从1开始
要求使用带哨兵的顺序查找算法
Input
第一行输入n#xff0c;表示队列有n个数据
第二行输入n个数据#xff0c;都是正整数#xff0c;用空格隔开
第三行输入t找出数值在队列中的位置队列位置从1开始
要求使用带哨兵的顺序查找算法
Input
第一行输入n表示队列有n个数据
第二行输入n个数据都是正整数用空格隔开
第三行输入t表示有t个要查找的数值
第四行起输入t个数值输入t行
Output
每行输出一个要查找的数值在队列的位置如果查找不成功输出字符串error
Sample
Input
8
33 66 22 88 11 27 44 55
3
22
11
99
Output
3
5
error
解题思路
想了解什么是哨兵查找算法首先可以看一下普通的顺序查找代码。
查找一个元素在数组中的下标如果存在就返回其下标
int NormalSearch(int target, int n)
{int length n;for (int i 1; i length; i) {if (arr[i] target) {return i;}}return 0;
}
与常规的顺序查找不同的是常规查找需要做两次判断判断下标是否超过长度和是否找到
哨兵查找算法只需要一个判断在数据量较大时可以提高效率
int sentrySearch(int target,int n)
{//如果第一个元素就是target直接返回1if (arr[1] target)return 1;//将第一个元素保存起来int temp arr[1];//将目标值放在第一个元素arr[1] target;int j n;while (target ! arr[j])--j;//查找完毕复原第一个元素arr[1] temp;return j 1 ? j : 0;
}
AC代码
#includeiostream
#includecstring
#includealgorithm
using namespace std;
const int N 10010;
int arr[N];
int sentrySearch(int target,int n)
{//如果第一个元素就是target直接返回1if (arr[1] target)return 1;//将第一个元素保存起来int temp arr[1];//将目标值放在第一个元素arr[1] target;int j n;while (target ! arr[j])--j;//查找完毕复原第一个元素arr[1] temp;return j 1 ? j : 0;
}int NormalSearch(int target, int n)
{int length n;for (int i 1; i length; i) {if (arr[i] target) {return i;}}return 0;
}int main()
{int n;while (cin n) {for (int i 1; i n; i) {cin arr[i];}int t;cin t;while (t--){int x;cin x;int ret sentrySearch(x, n);if (ret)cout ret endl;else cout error endl;}}return 0;
}
