A : DS静态查找之顺序查找

Description

给出一个队列和要查找的数值，找出数值在队列中的位置，队列位置从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代码

#include<iostream>
#include<cstring>
#include<algorithm>
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;
}