DSP

查找数组元素-简单二分

2019-07-13 15:33发布

站内文章 / DSP
9411 0 1668
限制内存：32768KB 题目： 查找数组元素 描述 给定一个数组, 快速判断是否出现了某个数. 输入格式 第一行, 一个整数n(1<=n<=100000), 表示数组元素的个数. 第二行, n个int类型整数, 表示数组的元素, 保证按照非递减的顺序给出. 第三行, 一个数字q(1<=q<=100000), 表示查询的个数. 以下q行, 每行一个整数x, 分别代表一个查询. 输出格式 对于每个查询, 如果x在数组中出现, 输出"Yes", 否则输出"No". 输入样例 5 1 3 5 7 9 3 1 2 3 输出样例 Yes No Yes #include using namespace std; int bs(int a[],int size,int p){ int l=0; int r=size-1; while(l<=r){ int mid=l+(r-l)/2; if(p==a[mid])return mid; else if(p>a[mid]) l=mid+1; else r=mid-1; }return -1; } int main() { int n,a[111111]; cin>>n; for(int i=0;icin>>a[i]; int t; cin>>t; while(t--){ int temp; cin>>temp; if(bs(a,n,temp)!=-1) cout<<"Yes"<else cout<<"No"<return 0; }

热门文章