4-10 二分查找

本题要求实现二分查找算法。

函数接口定义：

Position BinarySearch( List Tbl, ElementType K );

其中List结构定义如下：

typedef int Position;typedef struct LNode *List;struct LNode {    ElementType Data[MAXSIZE];    Position Last; /* 保存线性表中最后一个元素的位置 */};

Tbl是用户传入的一个线性表，其中ElementType元素可以通过>>、====、<<进行比较，并且题目保证传入的数据是递增有序的。函数BinarySearch要查找K在Tbl中的位置，即数组下标（注意：元素从下标1开始存储）。找到则返回下标，否则返回一个特殊的失败标记NotFound。

 

输入样例1：

512 31 55 89 10131

输出样例1：

2

输入样例2：

326 78 23331

输出样例2：

0 代码：

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 using namespace std; 6 #define MAXSIZE 10 7 #define NotFound 0 8 typedef int ElementType; 9 10 typedef int Position;11 typedef struct LNode *List;12 struct LNode {13     ElementType Data[MAXSIZE];14     int Last; /* 保存线性表中最后一个元素的位置 */15 };16 17 List ReadInput(); /* 裁判实现，细节不表。元素从下标1开始存储 */18 Position BinarySearch( List Tbl, ElementType K );19 20 int main()21 {22     List Tbl;23     ElementType K;24     Position P;25     Tbl = ReadInput();26     scanf("%d", &K);27     P = BinarySearch( Tbl, K );28     printf("%d\n", P);29     30     return 0;31 }32 List ReadInput()33 {34     int num;35     List L=(List)malloc(sizeof(LNode));36     L->Last=1;37     cin>>num;38     for(int i=1;i<=num;i++)39     {40         cin>>L->Data[i];41         L->Last=L->Last+1;42     }43     return L;44 }45 46 int BinarySearch( List Tbl, ElementType K)47 {48     int right=Tbl->Last,left=1,mid;49     if(Tbl==NULL) return 0;50     else {51         while(left<=right)52         {53             mid=(left+right)/2;54             if(K==Tbl->Data[mid])55             {56                 return mid;57             }58             else if(K
         
          Data[mid])59             {60                 right=mid-1;61             }62             else{63                 left=mid+1;64             }65         }66     }67     return NotFound;68 }