文章目录
题目
给一个严格递增数列，函数 i n t S e a r c h B i n ( S S T a b l e T , K e y T y p e k ) int Search_Bin(SSTable T, KeyType k) 用来二分地查找k在数列中的位置。
函数接口定义
int Search_Bin(SSTable T, KeyType k)
其中 T T 是有序表， k k 是查找的值。
裁判测试程序样例
#include <iostream> using namespace std; #define MAXSIZE 50 typedef int KeyType; typedef struct { KeyType key; } ElemType; typedef struct { ElemType *R; int length; } SSTable; void Create(SSTable &T) { int i; T.R = new ElemType[MAXSIZE + 1]; cin >> T.length; for (i = 1; i <= T.length; i++) cin >> T.R[i].key; } int Search_Bin(SSTable T, KeyType k); int main() { SSTable T; KeyType k; Create(T); cin >> k; int pos = Search_Bin(T, k); if (pos == 0) cout << "NOT FOUND" << endl; else cout << pos << endl; return 0; } /* 请在这里填写答案 */
输入格式
第一行输入一个整数 n n ，表示有序表的元素个数，接下来一行 n n 个数字，依次为表内元素值。 然后输入一个要查找的值。
输出格式
输出这个值在表内的位置，如果没有找到，输出 " N O T F O U N D " "NOT FOUND" 。
输入样例
5
1 3 5 7 9
7
输出样例
4
输入样例
5
1 3 5 7 9
10
输出样例
NOT FOUND
思路
因为是有序数列，所以可以直接开始查找。首先判断 K K 与有序数列 T T 的中间值的大小，如果 K K 大于中间值则直接开始查找后面的数列，依旧是查找后面数列的中间值与 K K 比较大小，以此类推之至找到 K K 或序列查找完毕，如果找到则返回该数字下标 + 1 +1 ，否则返回 0 0 ；如果 K K 小于中间值则直接开始查找前面的数列依旧是查找后面数列的中间值与 K K 比较大小，以此类推之至找到 K K 或序列查找完毕，如果找到则返回该数字下标 + 1 +1 ，否则返回 0 0 即可。折半查找也叫二分查找，更多 查找算法 可点击跳转查看。
完全代码
#include <iostream> using namespace std; #define MAXSIZE 50 typedef int KeyType; typedef struct { KeyType key; } ElemType; typedef struct { ElemType *R; int length; } SSTable; void Create(SSTable &T) { int i; T.R=new ElemType[MAXSIZE+1]; cin>>T.length; for(i=1;i<=T.length;i++) cin>>T.R[i].key; } int Search_Bin(SSTable T, KeyType k); int main () { SSTable T; KeyType k; Create(T); cin>>k; int pos=Search_Bin(T,k); if(pos==0) cout<<"NOT FOUND"<<endl; else cout<<pos<<endl; return 0; } /* 请在这里填写答案 */ int Search_Bin(SSTable T, KeyType k) { int i = 1, j = T.length; int mid; while (i <= j) { mid = (i + j) / 2; if (T.R[mid].key == k) return mid; if (T.R[mid].key > k) j = mid - 1; if (T.R[mid].key < k) i = mid + 1; } return 0; }
AC代码
int Search_Bin(SSTable T, KeyType k) { int i = 1, j = T.length; int mid; while (i < j) { mid = (i + j) / 2; if (T.R[mid].key == k) return mid; if (T.R[mid].key > k) j = mid - 1; if (T.R[mid].key < k) i = mid + 1; } return 0; }