自动搬运

查看原文

来自洛谷，原作者为

	一只大龙猫 嗷~呜！

搬运于2025-08-24 21:05:45，当前版本为作者最后更新于2021-07-06 14:41:38，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

原题传送门

对于这道题，我们固然可以一个一个去查找（即“顺序查找法”），但我们还可以用更优的方法——哨兵查找法。

先看一下代码。

#include<iostream>
using namespace std;
int n,a[20000],x,p;
int main(){
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>a[i];
	}
	cin>>x;
	a[n]=x;
	while(a[p]!=x)p++;
	if(p==n)cout<<"-1";
	else cout<<p;
	return 0;
}

“哨兵”指的就是 $a_n \gets x$ 一句中放在 $a_n$ 里的数。只要把 $x$ 放在 $a_n$ 里，当 $p=n$ 时就一定能找到 $x$，不会出现 $p > n$ 的情况。因此，我们就不用在while循环中确认 $p$ 的值是否达到了 $n$。

换句话说，我们把原来的

while(p<n){
	if(a[p]==x){
		cout<<p;
		return 0;
	}
	p++;
}
cout<<"-1";
return 0;

写成了

while(a[p]!=x)p++;
if(p==n)cout<<"-1";
else cout<<p;
return 0;

不但使代码看上去更加简洁，还省去判断 $p$ 是否等于 $n$ 的语句，节约了大约 $1 \over 4$ 的时间。在 $n ≤ 10000$ 时，节约的时间还不明显。但当 $n$ 达到 $1 \times 10^5$ 甚至是 $1 \times 10^6$ 时，函数的执行时间就会有显著差距了。

参考文献