顺序查简单的从头到尾的查，对数据没有要求，而折半查要求查的数据是按顺序排列的，然后中间数，若中间数大，则把中间数当成最后一个数他们的中间数。反之，则把中间数当成第一个数。他们的中间数。这样，一直下去，直到到或者中间数和第一个数或者最后一个数相等。它较顺序查，效率较高。
依据顺序查算法和折半查算法的特点，对下面的两个查表选择一个合适的算法，设计出完整的C源程序。并完成问题：
查表1：{ 8，15，19，26，33，41，47， 52，64，90 }，查key = 41
查表2：{12，76，29，15，62，35，33，89，48金瓶梅有几个版本，20 }，查key =35
查key=41的算法： 比较次数：
查key=35的算法： 比较次数：
查key=41的算法：折半查法 比较次数：3次
查key=35的算法：顺序查法 比较次数：6次
顺序查算法实现代码：
int SequenceSearch(int a[], int n, int key)
{ int i=0,cnt=0;
for (i=0; i<n; i++)
{cnt++;
if (a[i] == key)
{printf("\nSequencial Search compare times:%d",cnt);
return key ;}
}
return -1;
}
l折半查算法实现代码：
int BinarySearch(int a[], int n, int key)
{
int low=0,high=n-1,mid=0;
int cnt=0;
while (low<=high)
{ cnt++;
mid = (low+high)/2;
printf("\ncompare %d with %d",a[mid],key);
if (a[mid] == key)
{printf("\nSequencial Search compare times:%d",cnt);
return key;
}
if (a[mid]>key)
{high=mid-1;}
else
{low=mid+1;}
}
return -1;}
/*折半查法例题1*/
#include<stdio.h>
西部妈妈网void main()
{
int a[10]={8,18,27,42,47,50,56,68,95,120};
int b=8; //要查的数
int min=0; int max=9;
int mid=(min+max)/2;
while(b!=a[mid])
{
if(b>a[mid])
{min=mid;mid=(min+max)/2;}
else if(b<a[mid])
{max=mid;mid=(min+max)/2;}
if(mid==min)寒暄语
break;
}
if(b==a[mid])
{printf("a[%d]=%d\n",mid,a[mid]);}
else if(b==a[max])
{printf("a[%d]=%d\n",max,a[max]);}
else
printf("没有此数\n");
}
/*折半查法例题2*/
#include <stdio.h>
int main(){
int key=0;
printf("请输入要查的数：");
scanf("%d",&key);
int data[10]={1,3,5,7,8,9,13,18,22,28};
int ret=BinarySearch(key,data);
if(ret>=0)
printf("\n %d 是数组中的第%d个数\n",key,ret+1); else
printf("\n %d在数组中未到！\n",key);
system("pause");
return 0;
}
int BinarySearch(int key,int data[])
{
int low=0,high=9,middle;
while( low>=middle ){ /*查结束条件*/
int middle= （low+high）/2 ; /*获取数组中间位置*/
if( key==data[middle] ) /*如查当前数据元素的值等于key*/
return middle; /*返回所在位置*/
if(key<data[middle]) /*如果若k小于当前数据元素的值音节带声调吗*/
high=(low+middle)/2 ; /*在数组的前半部继续查*/
else
low=(middle+high)/2 /*在数组的后半部继续查*/
}
return -1; /*返回查不成功标记*/
}
/*简单排序法*/
#include<stdio.h>
#define N 6
void swap(int *a, int *b)
{int t;
t=*a;
*a=*b;
*b=t;}
void main()
{int a[6]={15,14,22,30,37,11};
int min;
for(int i=0;i<N-1;i++)
{min=i;
for(int j=i+1;j<N;j++)
{if(a[i]<a[j])
min=j;
}
swap(a+i,a+min);
}
for(i=0;i<N;i++)
printf("%d ",a[i]);
}
2013年高考题
36. 折半查也称为二分查，适用于有序数组，其查的基本过程是：先确定待查记录所在的范围，然后逐步缩小范围，直到到，或不到该记录为止。假定数组按照升序排列，对于给定值K，从数组中间位置开始比较，如果当前数据元素的值等于k，则查成功。否则，若k小于当前数据元素的值，则在数组的前半部继续查；反之，则在数组的后半部继续查，依次重复进行，直至获得查成功或不成功的结果。请补充完成下列程序中的相应部分：
#include <stdio.h>
int main(){
int key=0;
printf("请输入要查的数：");
scanf("%d",&key);
int data[10]={1,3,5,7,8,9,13,18,22,28};
int ret=BinarySearch(key,data);
if(ret>=0)
printf("\n %d 是数组中的第%d个数\n",key,ret+1);
else
printf("\n %d在数组中未到！\n",key);鲁米诺
system("pause");
return 0;
}
int BinarySearch(int key,int data[]){
int low=0,high=9,middle;
while(){ /*查结束条件*/
int middle= ; /*获取数组中间位置*/
if() /*如查当前数据元素的值等于k*/
return middle; /*返回所在位置*/
if(key<data[middle]) /*如果若k小于当前数据元素的值*/
; /*在数组的前半部继续查*/
else
/*在数组的后半部继续查*/
}
return -1; /*返回查不成功标记*/
}
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议