[刷题] 二分查找

浙大mooc习题：
 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 
 4 #define MAXSIZE 10
 5 #define NotFound 0
 6 typedef int ElementType;
 7 
 8 typedef int Position;
 9 typedef struct LNode *List;
10 Position BinarySearch( List L, ElementType X );
11 
12 struct LNode {
13     ElementType Data[MAXSIZE];
14     Position Last; /* 保存线性表中最后一个元素的位置 */
15 };
16 
17 List ReadInput(); /* 裁判实现，细节不表。元素从下标1开始存储 */
18 Position BinarySearch( List L, ElementType X );
19 
20 int main()
21 {
22     List L;
23     ElementType X;
24     Position P;
25 
26     L = ReadInput();
27     scanf("%d", &X);
28     P = BinarySearch( L, X );
29     printf("%d
", P);
30 
31     return 0;
32 }
33 Position BinarySearch( List L, ElementType X ){
34     int p = 0;
35     int l = 1;
36     int r =  L->Last;
37     int num = r/2;
38     while(num--){
39         int mid = (l + r)/2;
40         if(L->Data[mid] == X){
41             p = mid;
42             break;
43         }
44         else if(L->Data[r] == X){
45             p = r;
46             break;
47         }
48         else if(L->Data[mid] > X)
49             r = mid;
50         else if(L->Data[mid] < X)
51             l = mid;
52     }
53     if(p == 0)
54         return NotFound;
55     return p;
56 }