6-13 折半查找（15 分）
给一个严格递增数列，函数int binSearch(SeqList T, KeyType k)用来二分地查找k在数列中的位置。
函数接口定义：
1
| int binSearch(SeqList T, KeyType k)
|
其中T是有序表，k是查找的值。
裁判测试程序样例：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| #include <iostream>
using namespace std;
#define MAXLEN 50
typedef int KeyType;
typedef struct
{ KeyType key;
} elementType;
typedef struct
{ elementType data[MAXLEN+1];
int len;
} SeqList;
void creat(SeqList &L)
{ int i;
cin>>L.len;
for(i=1;i<=L.len;i++)
cin>>L.data[i].key;
}
int binSearch(SeqList T, KeyType k);
int main ()
{ SeqList L; KeyType k;
creat(L);
cin>>k;
int pos=binSearch(L,k);
if(pos==0) cout<<"NOT FOUND"<<endl;
else cout<<pos<<endl;
return 0;
}
|
输入格式：
第一行输入一个整数n，表示有序表的元素个数，接下来一行n个数字，依次为表内元素值。 然后输入一个要查找的值。
输出格式：
输出这个值在表内的位置，如果没有找到，输出”NOT FOUND”。
输入样例：
输出样例：
输入样例：
输出样例：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
| #include <iostream>
using namespace std;
#define MAXLEN 50
typedef int KeyType;
typedef struct
{ KeyType key;
} elementType;
typedef struct
{ elementType data[MAXLEN+1];
int len;
} SeqList;
void creat(SeqList &L)
{ int i;
cin>>L.len;
for(i=1;i<=L.len;i++)
cin>>L.data[i].key;
}
int binSearch(SeqList T, KeyType k);
int main ()
{ SeqList L; KeyType k;
creat(L);
cin>>k;
int pos=binSearch(L,k);
if(pos==0) cout<<"NOT FOUND"<<endl;
else cout<<pos<<endl;
return 0;
}
int binSearch(SeqList T, KeyType k){
int mid;
int i = 1,j = T.len;
while(i<j){
mid = (i+j)/2;
if(T.data[mid].key == k){
return mid;
}
if (T.data[mid].key>k){
j = mid -1;
}
if(T.data[mid].key < k){
i = mid +1;
}
}
return 0;
}
|
