B2093 查找特定的值题解

一只大龙猫 · 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 时，函数的执行时间就会有显著差距了。

参考文献

B2093 查找特定的值 题解

B2093 查找特定的值题解