6-13 折半查找 (15分)

语言要求使用C++，然后发现用c语言的格式也可以过，嗯~ o(￣▽￣)o这大概就是兼容吧 折半查找还是很套路的，大概就是定义好mid，low，high三个变量，设定一个while循环，让它们不断缩小范围。一开始的high设定下标应该是length-1，不过测试的时候写的length也通过了。不过既然是位置嘛，下标还是要减一下的。

给一个严格递增数列，函数int Search_Bin(SSTable T, KeyType k)用来二分地查找k在数列中的位置。

函数接口定义： int Search_Bin(SSTable T, KeyType k) 其中T是有序表，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个数字，依次为表内元素值。 然后输入一个要查找的值。

输出格式： 输出这个值在表内的位置，如果没有找到，输出"NOT FOUND"。

输入样例： 5 1 3 5 7 9 7 输出样例： 4 输入样例： 5 1 3 5 7 9 10 输出样例： NOT FOUND

int Search_Bin(SSTable T, KeyType k){ int low=0; int high=T.length-1; int mid; while(low<=high){ int mid=(low + high) / 2; if (k == T.R[mid].key){ return mid; }else if(k>T.R[mid].key){ low=mid+1; }else{ high=mid-1; } } return 0; }