#include <stdio.h>
#include <stdlib.h>
typedef int InfoType;

#define n 10						//假設(shè)的文件長度
typedef int KeyType;				//假設(shè)的關(guān)鍵字類型
typedef struct{						//記錄類型
	KeyType key;					//關(guān)鍵字項(xiàng)
	InfoType otherinfo;				//其它數(shù)據(jù)項(xiàng)，此類型依賴于應(yīng)用
}NodeType;
typedef NodeType SeqList[n+1];		//0號單元用作哨兵

void main()
{
	int BinSearch(SeqList R,KeyType k);
	void PrintList(SeqList L);
	SeqList L;
	int i,x;
	L[1].key=rand()%10;
	for (i=2;i<=n;i++)
		L[i].key=rand()%10+L[i-1].key;
	PrintList(L);			//打印順序表
	printf("輸入要查找的值：");
	scanf("%d",&x);
	i=BinSearch(L,x);		//順序表查找
	if (i==0)
		printf("未找到%d!\n",x);
	else
		printf("找到%d，在第%d個位置上!\n",x,i);
}

//順序表的打?。?void PrintList(SeqList L)
{	int i;
	for (i=1;i<=n;i++)
		printf("%d  ",L[i].key);
	printf("\n");
}

int BinSearch(SeqList R,KeyType k)
{	//在有序表R[1..n]中進(jìn)行二分查找，成功時返回結(jié)點(diǎn)的位置，失敗時返回零
	int low=1,high=n,mid;			//置當(dāng)前查找區(qū)間上、下界的初值
	while(low<=high) {				//當(dāng)前查找區(qū)間R[low..high]非空
		mid=(low+high)/2;
		if(R[mid].key==k) return mid;//查找成功返回
		if(R[mid].key>k)
			high=mid-1;				//繼續(xù)在R[low..mid-1]中查找
		else
			low=mid+1;				//繼續(xù)在R[mid+1..high]中查找
	}
	return 0;						//當(dāng)low>high時表示查找區(qū)間為空，查找失敗
}