6-13 折半查找

给一个严格递增数列，函数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;
}

/* 请在这里填写答案 */

输入样例1

5
1 3 5 7 9
7

输出样例1

4

输入样例2

5
1 3 5 7 9
10

输出样例2

NOT FOUND

分析及答案

函数题的最后一题，也是和前面风格完全不同的一题（出题单位和前面不同），还是唯一一道要求用C++的题目，但众所周知C++向下兼容C，所以用C语言去实现这个函数也是没有问题的。

最终的输出已经在裁判程序里实现了，函数只需要返回0（查找失败）或者对应的位置值（查找成功），并更新传入的k变量值即可。虽然题目说的是折半查找，但是单就这一题的测试点来看，就算使用遍历查找说不定也能过。

int Search_Bin(SSTable T,KeyType k){
    //定义左右指针，注意裁判程序是从1开始存数值的，函数里也要保持一致
    int i=1,j=T.length;
    while(1){
        //如果和左右指针值相同，返回对应位置
        if(k==T.R[i].key)
            return i;
        if(k==T.R[j].key)
            return j;
        //左右指针相邻也没有找到，返回0
        if(j-i==1)
            return 0;
        //数列严格递增，根据题目条件来制定折半规则
        if(k>T.R[(i+j)/2].key)
            i=(i+j)/2;
        else
            j=(i+j)/2;
    }
}