折半查找

给一个严格递增数列，函数Search_Bin(SSTable ST, KeyType key)用来二分地查找key在数列中的位置。
其中ST是有序表，key是查找的值
函数接口定义：

1
Search_Bin(SSTable ST, KeyType key)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <stdio.h>
#include <stdlib.h>

#define NOT_FOUND -1

typedef int KeyType;

typedef struct {
    KeyType key;
}SElemType;

typedef struct {
    SElemType *elem;
    int length;
}SSTable;

int Search_Bin(SSTable ST, KeyType key);

int main () {
    SSTable T;

    scanf("%d", &T.length);
    T.elem = (SElemType *) malloc ((T.length + 1) * sizeof(SElemType));

    for(int i = 1; i <= T.length; ++ i)
        scanf("%d", &T.elem[i].key);

    KeyType key;
    scanf("%d", &key);

    int pos = Search_Bin(T, key);
    if(pos == NOT_FOUND) puts("NOT FOUND");
    else printf("%d\n", pos);
    return 0;
}
int Search_Bin(SSTable ST, KeyType key)
{
    int high;
    int low;
    low =1;
    high = ST.length;
    while(low <= high)
    {
        int mid=(high+low)/2;
        if(ST.elem[mid].key==key)
        {
            return mid;
        }
        else if(ST.elem[mid].key>key)
        {
        high=mid-1;
        }
        else
        {
        low=mid+1;
        }
    }

    return -1;
}