Attention: 如果喜歡我寫(xiě)的文章矾屯，歡迎來(lái)我的github主頁(yè)給star
Github：github.com/MuziJin
給一個(gè)嚴(yán)格遞增數(shù)列，函數(shù)int binSearch(SeqList T, KeyType k)用來(lái)二分地查找k在數(shù)列中的位置偿荷。
函數(shù)接口定義：
int binSearch(SeqList T, KeyType k);
其中T是有序表优妙，k是查找的值助琐。
裁判測(cè)試程序樣例：
#include <iostream>
using namespace std;
#define MAXLEN 50
typedef int KeyType;
typedef struct
{ KeyType key;
} elementType;
typedef struct
{ elementType data[MAXLEN+1];
int len;
} SeqList;
void creat(SeqList &L)
{ int i;
cin>>L.len;
for(i=1;i<=L.len;i++)
cin>>L.data[i].key;
}
int binSearch(SeqList T, KeyType k);
int main ()
{ SeqList L; KeyType k;
creat(L);
cin>>k;
int pos=binSearch(L,k);
if(pos==0) cout<<"NOT FOUND"<<endl;
else cout<<pos<<endl;
return 0;
}
/* 請(qǐng)?jiān)谶@里填寫(xiě)答案 */
輸入格式：
第一行輸入一個(gè)整數(shù)n眉抬，表示有序表的元素個(gè)數(shù)贯吓，接下來(lái)一行n個(gè)數(shù)字，依次為表內(nèi)元素值蜀变。 然后輸入一個(gè)要查找的值。
輸出格式：
輸出這個(gè)值在表內(nèi)的位置介评，如果沒(méi)有找到库北，輸出"NOT FOUND"爬舰。
輸入樣例：
5
1 3 5 7 9
7
輸出樣例：
4
輸入樣例：
5
1 3 5 7 9
10
輸出樣例：
NOT FOUND
Code
int binSearch(SeqList T, KeyType k)
{
int i = 1;
int j = T.len;
int mid;
int loc = 0;
while( i<j)
{
mid = ( i+j)/2;
if( T.data[mid].key == k)
{
loc = mid;
break;
}
else if( T.data[mid].key > k)
j = mid-1;
else
i = mid+1;
}
return loc;
}
轉(zhuǎn)載請(qǐng)注明出處：github.com/MuziJin
