king.cpp

c二分法源码下载

#include<stdio.h>
#include<stdlib.h>
#define EQ(a,b) ((a)==(b))
#define LT(a,b) ((a)<(b))
#define LQ(a,b) ((a)<=(b))

typedef int KeyType;

typedef struct{
	KeyType key;
}ElemType;

typedef struct
 {
   ElemType *elem;
   int length;
 }SSTable;


Creat(SSTable &ST,int n)
{ 
   int i;
   ElemType m;
   ST.elem=(ElemType *)malloc((n+1)*sizeof(ElemType)); 
   if(!ST.elem)
     return 0;
   printf("\n输入递增有序表元素:");
   for(i=1;i<=n;i++)
   {
	   scanf("%d,",&m);
		*(ST.elem+i)=m;
   }
   ST.length=n;
   return 1;
}


int Search(SSTable &ST, KeyType key)
 {
  
   int low,high,mid;
   low=1; 
   high=ST.length;
   while(low<=high)
   {
     mid=(low+high)/2;
     if EQ(key,ST.elem[mid].key) 
       return mid;
     else if LT(key,ST.elem[mid].key)
       high=mid-1; 
     else
       low=mid+1; 
   }
   return 0; 
 }

void main()
{
	int n,m;
	KeyType key;
	SSTable ST;
	printf("\n请输入元素个数:");
	scanf("%d",&n);
	Creat( ST, n);
	printf("\n请输入关键元素key:");
	scanf("%d",&key);
	m=Search(ST,key);
	if(!m)
	printf("\n表中没有关键字");
	else
	printf("\n关键元素为第%d个元素",m);
}