ACM 递归递推练习:二分法查找找到中间的数值,如果 key 目标数值大于中间值,则返回 mid+1 与 n 区间。
如果小于,则返回 mid-1 与起始位置区间,
- //由于输出次数较多,用cout容易超时,用printf则可省时。#includeint a[3000001];int search(int a[],int l,int r,int key) //l代表首位,r代表最后一位{int low=l,high=r,mid;if(l<=r){mid=low+(high-low)/2;if(a[mid]==key) return mid;if(a[mid]>key)return search(a,low,mid-1,key);if(a[mid] return search(a,mid+1,high,key);}return -1;}int main(){int n,q,i,j,k;scanf("%d",&n);for(i=1;i<=n;i++){scanf("%d",&a[i]);}scanf("%d",&q);for(j=0;j {scanf("%d",&k);printf("%d\n",search(a,1,n,k));}return 0;}Description给出含有n个数的升序序列,保证序列中的数两两不相等,这n个数编号从1 到n。然后给出q次询问,每次询问给出一个数x,若x存在于此序列中,则输出其编号,否则输出-1。Input单组输入。首先输入一个整数n(1 <= n && n <= 3000000),接下的一行包含n个数。再接下来的一行包含一个正整数q(1 <= q && q <= 10000),表示有q次询问。再接下来的q行,每行包含一个正整数x。Output对于每次询问,输出一个整数代表答案。Sample Input51 3 5 7 93158Sample Output13-1
就爱阅读 www.92to.com 网友整理上传, 为您提供最全的知识大全, 期待您的分享,转载请注明出处。
来源: http://www.92to.com/bangong/2017/04-12/20344833.html