哨兵的作用

哨兵的作用:在查找方向的尽头设置“哨兵”免去了在查找过程中每次比较后都要判断查找位置是否越界的小技巧,在总数居较多时,效率提高很大。

未使用哨兵:

#include<bits/stdc++.h>
using namespace std;
const int maxn=1010;
#define inf 0x3fffffff
int main(){
    int n,key=3;
    int num[maxn];
    for(int i=1;i<5;i++){//每次都要执行i<5判断
        num[i]=i;
    }
    for(int i=1;i<5;i++){
        if(num[i]==key){
            cout<<i<<endl;
            break;
        }
    }
    return 0;
}

使用哨兵:

#include<bits/stdc++.h>
using namespace std;
const int maxn=1010;
#define inf 0x3fffffff
int main(){
    int n,key=3;
    int num[maxn];
    for(int i=1;i<5;i++){
        num[i]=i;
    }
    num[0]=key;//使用哨兵
    int i=4;
    while(num[i]!=key){
        i--;
    }
    if(i==0){
        cout<<-1<<endl;
    }
    else{
        cout<<i<<endl;
    }
    return 0;
}

 

上一篇:numpy大气磅礴


下一篇:Javaweb