swust oj 1010

折半查找的实现

1000(ms)

10000(kb)

2877 / 11213

编写程序实现折半查找算法。

输入

第一行是查找表的长度n
第二行是查找表中的数据元素 ；
第三行是要查找的数据元素的关键字.

输出

查找成功返回位序，不成功返回-1 ,第二行为比较的次数。

样例输入

11
5 13 19 21 37 56 64 75 80 88 92
100

样例输出

-1
4

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstdio>
 4 #include<cstdlib>
 5 #include<cstring>
 6 #include<cmath>
 7 using namespace std;
 8 int x;
 9 int findx=-1;
10 
11 int find(int arr[],int l,int r)
12 {
13     static int k=0;
14     if(l>r)
15         return 0;
16     int s=(l+r)>>1;
17     if(arr[s]>x)
18         find(arr,l,s-1);
19     else if(arr[s]<x)
20         find(arr,s+1,r);
21     else
22         findx=s;
23     k++;
24     return k;
25 }
26 
27 int main()
28 {
29     int n;
30     cin>>n;
31     int *p=new int[n];
32     for(int i=0;i<n;i++)
33         cin>>*(p+i);
34     cin>>x;
35     int y=find(p,0,n-1);
36     cout<<findx<<endl;
37     cout<<y;
38     delete(p);
39     return 0;
40 }