本題要求實現(xiàn)二分查找算法。
函數(shù)接口定義：
Position BinarySearch( List L, ElementType X );其中
List結(jié)構(gòu)定義如下：typedef int Position; typedef struct LNode *List; struct LNode { ? ElementType Data[MAXSIZE]; ? Position Last; /* 保存線性表中最后一個元素的位置 */ };
L是用戶傳入的一個線性表配乓，其中ElementType元素可以通過>、==敞葛、<進行比較腺占，并且題目保證傳入的數(shù)據(jù)是遞增有序的。函數(shù)BinarySearch要查找X在Data中的位置妙黍，即數(shù)組下標（注意：元素從下標1開始存儲）。找到則返回下標瞧剖，否則返回一個特殊的失敗標記NotFound拭嫁。裁判測試程序樣例：
#include <stdio.h> #include <stdlib.h> #define MAXSIZE 10 #define NotFound 0 typedef int ElementType; typedef int Position; typedef struct LNode *List; struct LNode { ? ElementType Data[MAXSIZE]; ? Position Last; /* 保存線性表中最后一個元素的位置 */ }; List ReadInput(); /* 裁判實現(xiàn)，細節(jié)不表抓于。元素從下標1開始存儲 */ Position BinarySearch( List L, ElementType X ); int main() { ? List L; ? ElementType X; ? Position P; L = ReadInput(); scanf("%d", &X); P = BinarySearch( L, X ); printf("%d\n", P); return 0; } /* 你的代碼將被嵌在這里 */輸入樣例1：
5 12 31 55 89 101 31輸出樣例1：
2輸入樣例2：
3 26 78 233 31輸出樣例2：
0
Position BinarySearch( List L, ElementType X )
{
Position p;
Position l,r;
l = 1;
r = L->Last;
p = (1+L->Last)/2;
while(l < r && L->Data[p]!=X){
if(X < L->Data[p]){
r = p-1;
}
else{
l = p+1;
}
p = (l+r)/2;
}
if(L->Data[p]==X){
return p;
}
else{
return NotFound;
}
}
