C语言编程之拆半查找法

[复制链接]
查看11 | 回复4 | 2010-7-12 13:44:16 | 显示全部楼层 |阅读模式
我刚接触C语言,有很多的问题,呵呵,希望高手们不吝赐教,呵呵,这次是关于拆半查找法的问题,大家应该都知道,可是我就是不理解这个程序是怎么实现的,希望高手们能指点一下,以下是程序代码:
#include
main()
{
char c,a[10]="abcdefghi";
int top,bot,mid;
printf("input c:\n");
scanf ("%c",&c);
printf ("c=\'%c\'\n",c);
for (top=0,bot=10;topa[mid]) top=mid+1;

else bot=mid-1;
}
if (top>bot) printf ("**\n");
}

回复

使用道具 举报

千问 | 2010-7-12 13:44:16 | 显示全部楼层
首先数组就得按从大到小或者从小到大先排列好,代码里面的数组已经按照从小到大的顺序排好了,这叫预排序,没有预排序就无法进行折半查找。。。。折半查找,你要先确定一个头和一个尾,就像上面的top与bot,而你要查找的数据肯定会在头与尾之间那段数组中(前提是数组里面一定含有你要查找的数据)。。。。那么为了加快查找速度,我们可以先拿头与尾中间的那个数据,与所要查找的数据(下面用c来表示该数据)进行比较,中间那个数的位置就在mid=(top+bot)/2。。。。举这样的例子吧,从1到100的数中查找c。。。。如果中间数50等于c,那就可以直接得出它在数组中的位置了,就是mid,代码if(c==a[mid])的作用就是这样。。。。
回复

使用道具 举报

千问 | 2010-7-12 13:44:16 | 显示全部楼层
备注:字母也有大小之分。先说一下算法的基本思想:在一个递增的数组中,如果要查找的数,比数组中间的数小,那么它肯定main(){ ch
回复

使用道具 举报

千问 | 2010-7-12 13:44:16 | 显示全部楼层
折半查找法,是对应已经排序的数组查找某个特定数的方法。以你给的题为例。一开始知道 c在a[0]-a[9]之间,把c和a[5]比较,如果c=a[5],就找到了如果c>a[5],就知道c在a[6]-a[9]之间了,top=6,bot=9否者c必然小于a[5]了,就去a[0]-a[4]搜索,top=0,bot=4;如此反复,查找c
回复

使用道具 举报

千问 | 2010-7-12 13:44:16 | 显示全部楼层
举个简单的例子吧,猜大小(幸福52那种),如果是0~100;你肯定先猜50,如果大了,你就猜25,如果小了,就猜37(25+25/2)。。。以此类推,明白原理了吧,这样的速度是很快的
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

主题

0

回帖

4882万

积分

论坛元老

Rank: 8Rank: 8

积分
48824836
热门排行