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;
}