题解 | 查找

//查找(二分查找)

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;

//设计compare函数(升序排列，左小右大)，sort默认升序，也可以不用写这个函数
bool compare(int lhs,int rhs){
    if(lhs<rhs){    //满足条件，不用交换，返回true
        return true;
    }else{  //需要交换，返回false
        return false;
    }
}

//二分查找
void md(vector<int> arr,int key,int n){ //传入数组，要查找的元素，数组长度
    int left=0; //左边left初始指向最左边元素，下标为0
    int right=n-1;  //右边right初始指向最右边元素，下标为n-1

    while(left<=right){  //左右边界相等的时候，也要判断一次
        int mid=(left+right)/2; //mid是中间位置元素下标
        if(arr[mid]>key){   //若key更小，则说明在左边
            right=mid-1;    //往左边走
        }else if(arr[mid]<key){ //若Key比中间值更大，说明在右边
            left=mid+1; //往右边走
        }else if(arr[mid]==key){  //相等说明找到了
            printf("YES\n");
            break;
        }
    }
    if(left>right){ //没找到
        printf("NO\n");
    }
}

//主函数
int main(){
    int n;  //n为数组长度
    while(scanf("%d",&n)!=EOF){
        vector<int> a(n);   //a数组长度为n
        for(int i=0;i<n;i++){   //输入数组元素
            scanf("%d",&a[i]);
        }

        int m;
        scanf("%d",&m); //m个要查找的数字
        vector<int> b(m);   //b数组用于记录要查找的数字
        for(int i=0;i<m;i++){   //输入要查找的数字
            scanf("%d",&b[i]);
        }

        sort(a.begin(),a.end(),compare);    //对a数组进行排序
        for(int i=0;i<m;i++){   //遍历b数组，在a数组里面查找它们
            md(a,b[i],n);  //二分查找
        }
    }

    return 0;
}