顺序查找、折半查找

顺序查找与折半查找的比较
顺序查找简单的从头到尾的查找，对数据没有要求，而折半 查找要求查找的
数据是按顺序排列的，然后找中间数，若中间数大，则把中间数当成最后一个数
找他们的中间数。反之，则把中间数当成第一个数。找他们的中间数。这样，一
直找下去，直到找到或者 中间数和第一个数或者最后一个数相等。它较顺序查找，
效率较高。
依据顺序查找算法和折半 查找算法的特点，对下面的两个查找表选择一个合适的
算法，设计出完整的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 {cnt++;
if (a[i] == key)
{printf(
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(
if (a[mid] == key)
{printf(
return key;
}
if (a[mid]>key)
{high=mid-1;}
else
{low=mid+1;}
}
return -1;}

1

*折半查找法例题1*
#include
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{max=mid;mid=(min+max)2;}
if(mid==min)
break;
}
if(b==a[mid])
{printf(
else if(b==a[max])
{printf(
else
printf(没有此数n
}
*折半查找法例题2*
#include
int main(){
int key=0;
printf(请输入要查找的数：
scanf(
int data[10]={1,3,5,7,8,9,13,18,22,28};
int ret=BinarySearch(key,data);
if(ret>=0)
printf(是数组中的第%d个数n
else
printf(在数组中未找到！n
system(
return 0;
}
int BinarySearch(int key,int data[])
{
int low=0,high=9,middle;
while( low>=middle ){ *查找结束条件*
int middle= （low+high）2 *获取数组中间位置*

2

if( key==data[middle] ) *如查当前数据元素的值等于
key*
return middle; *返回所在位置*
if(key high=(low+middle)2 *在数组的前半部继续查找*
else
low=(middle+high)2 *在数组的后半部继续查找*
}
return -1; *返回查找不成功标记*
}

*简单排序法*
#include
#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{min=i;
for(int j=i+1;j{if(a[i]min=j;
}
swap(a+i,a+min);
}
for(i=0;iprintf(
}
2013年高考题
36. 折半查找也称为二分查找， 适用于有序数组，其查找的基本过程是：先确定
待查记录所在的范围，然后逐步缩小范围，直到找到，或 找不到该记录为止。
假定数组按照升序排列，对于给定值K，从数组中间位置开始比较，如果当
前数据元素的值等于k，则查找成功。否则，若k小于当前数据元素的值，
则在数组的前半部继续查找； 反之，则在数组的后半部继续查找，依次重复
进行，直至获得查找成功或不成功的结果。请补充完成下列 程序中的相应部
分：
#include

3

int main(){
int key=0;
printf(请输入要查找的数：
scanf(
int data[10]={1,3,5,7,8,9,13,18,22,28};
int ret=BinarySearch(key,data);
if(ret>=0)
printf(是数组中的第%d个数n
else
printf(在数组中未找到！n
system(
return 0;
}
int BinarySearch(int key,int data[]){
int low=0,high=9,middle;
while( ① ){ *查找结束条件*
int middle= ② *获取数组中间位置*
if( ③ ) *如查当前数据元素的值等于k*
return middle; *返回所在位置*
if(key ④ *在数组的前半部继续查找*
else
⑤ *在数组的后半部继续查找*
}
return -1; *返回查找不成功标记*
}
4