二分查找

数据结构实验之查找四：二分查找 Time Limit: 20ms Memory limit: 65536K 有疑问？点这里^_^ 题目描述 在一个给定的无重复元素的递增序列里，查找与给定关键字相同的元素，若存在则输出找到的位置,不存在输出-1。 输入 一组输入数据，输入数据第一行首先输入两个正整数n ( n < = 10^6 )和m ( m < = 10^4 )，n是数组中数据元素个数，随后连续输入n个正整数，输入的数据保证数列递增。 随后m行输入m个待查找的关键字key 输出 若在给定的序列中能够找到与关键字key相等的元素，则输出位序(序号从0开始)，否则输出-1。 示例输入 8 3 4 6 8 9 13 20 21 22 6 8 17 示例输出 1 2

-1

/* 非递归方法*/

# include <bits/stdc++.h> using namespace std; void Find(int len,int a[],int key); int a[1000000]; int main() { int n,m,i,key; cin>>n>>m; for(i=0;i<n;i++) { cin>>a[i]; } while(m--) { cin>>key; Find(n,a,key); } return 0; } void Find(int len,int a[],int key) { int lowerBound = 0; int upperBound = len - 1; int midPoint = -1; int index = -1; while(lowerBound <= upperBound) // 数组中还有元素 { midPoint = (lowerBound + upperBound)/2;//取中间值比较 if(a[midPoint] == key) { index = midPoint; break; } else if(a[midPoint] < key) // 中间值比key小,说明要找的元素在右区间 { lowerBound = midPoint + 1; } else// 中间值比key大,说明要找的值在左区间 { upperBound = midPoint - 1; } } cout<<index<<endl; } /*递归方法*/ # include <stdio.h> int a[1000000]; int binsearch(int l,int h,int key) { int low,high,mid; low=l; high=h; mid=(low+high)/2; if(low>high)//没有元素 { return -1; } if(a[mid]==key) return mid; else if(a[mid]<key) return binsearch(mid+1,high,key); else if(a[mid]>key) return binsearch(low,mid-1,key); else return -1; } int main() { int n,m,i,key,res; scanf("%d%d",&n,&m); for(i=0;i<n;i++) scanf("%d",&a[i]); while(m--) { scanf("%d",&key); res=binsearch(0,n-1,key); printf("%d\n",res); } }