有序表上二分查找.c

有序表上二分查找,数据结构中的一种

#include <stdio.h>

#define MAXSIZE 100
#define KEYTYPE int 

typedef struct
{
    KEYTYPE key;
}SSELEMENT;

typedef struct
{
    SSELEMENT r[MAXSIZE];
	int len;
}SSTABLE;

int search_bin(KEYTYPE k,SSTABLE *st)
{
	//有序表上二分查找
	int low,high,mid;
	low=1;high=st->len;
	//low=1表示元素从下标为1的单元放起
	//high=st->len表示最后一个元素所在下标
	while(low<=high)//low<=high为继续查找的条件
	{
		mid=(low+high)/2;
		if(k==st->r[mid].key) return mid;//k==st->r[mid].key表示查找成功
		else if(k<st->r[mid].key)
			    high=mid-1;
		else low=mid+1;
	}
	return 0;//查找不成功，返回0
}

main()
{
	//顺序表上查找元素
	SSTABLE a;
	int i,j,k;
	printf("请输入有序表元素，元素为整型量（从小到大输入），用空格分开，-99为结束标志：\n");
	j=0;k=1;i=0;scanf("%d",&i);
	while(i!=-99)//输入有序表元素
	{
		j++;
		a.r[k].key=i;
		k++;
		scanf("%d",&i);
	}	
	a.len=j;
	printf("\n有序表元素列表显示：");
	for(i=1;i<=a.len;i++)
		printf("%d  ",a.r[i].key);
	printf("\n");
	printf("\n输入待查元素关键字：");
	scanf("%d",&i);
	k=search_bin(i,&a);
	if(k==0)printf("表中待查元素不存在\n\n");
	else printf("表中待查元素存在\n\n");	
}