{ int low=1,high=*n,mid,i
while(low<=high)
{ mid= (low+high)/2
if (x.key<r[mid].key)high=mid-1
else low=mid+1
}
for(i=*ni>=mid i--)
r[i+1]=r[i]
r[mid]=x
*n++
}
二分查找又称为折半查找,是一种效率较高的查找方法,其中查找的关键是要求线性表是有序表,即表中的元素按关键字有序。例如:
int BinSearch(SeqList R,int n, KeyType k)
{
int low=0, high =n-1,mid
while(low<=high)
{
mid =(low+high)/2
if(R[mid].key==k)
return mid+1
if(R[mid].key>k)
return mid-1
else
low=mid+1
}
return 0
}
struct list{int key}/*定义结构类型*/typedef struct list SeqList,DataType
void BinInsert(SeqList r[],int *n,DataType x)
{ int low=1,high=*n,mid,i
while(low<=high)
{ mid=(low+high)/2
if (x.key<r[mid].key)high=mid-1
else low=mid+1
}
for(i=*ni>=midi--)
r[i+1]=r[i]
r[mid].key=x.key/*插入元素*/
}
main()
{
SeqList a[11]int i,nDataType y
n=0
for(i=0i<10i++)/*输入数据*/
{a[i].key=i+1n++}
printf("before sort :")
for(i=0i<10i++)/*排序前的数组*/
{printf("%4d",a[i].key)}
printf("\ninput elem(y)=")/*输入要插入的元素*/
scanf("%d",&y.key)
BinInsert(a,&n,y)
printf("\nafter sort :")
for(i=0i<11i++)/*输出排序后的数组*/
printf("%4d",a[i].key)getch()
}