折半查找.cpp

这里面包括数据结构多数的算法

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

#define n 10						//假设的文件长度
typedef int KeyType;				//假设的关键字类型
typedef struct{						//记录类型
	KeyType key;					//关键字项
	InfoType otherinfo;				//其它数据项，此类型依赖于应用
}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]中进行二分查找，成功时返回结点的位置，失败时返回零
	int low=1,high=n,mid;			//置当前查找区间上、下界的初值
	while(low<=high) {				//当前查找区间R[low..high]非空
		mid=(low+high)/2;
		if(R[mid].key==k) return mid;//查找成功返回
		if(R[mid].key>k)
			high=mid-1;				//继续在R[low..mid-1]中查找
		else
			low=mid+1;				//继续在R[mid+1..high]中查找
	}
	return 0;						//当low>high时表示查找区间为空，查找失败
}