我刚接触C语言,有很多的问题,呵呵,希望高手们不吝赐教,呵呵,这次是关于拆半查找法的问题,大家应该都知道,可是我就是不理解这个程序是怎么实现的,希望高手们能指点一下,以下是程序代码:
#include<stdio.h>
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;top<=bot;)
{
mid=(top+bot)/2;
if (c==a[mid])
{
printf("the position is %d\n",mid+1);
break;
}
else if (c>a[mid]) top=mid+1;
else bot=mid-1;
}
if (top>bot) printf ("**\n");
}
首先数组就得按从大到小或者从小到大先排列好，代码里面的数组已经按照从小到大的顺序排好了，这叫预排序，没有预排序就无法进行折半查找。。。。
折半查找，你要先确定一个头和一个尾，就像上面的top与bot，而你要查找的数据肯定会在头与尾之间那段数组中（前提是数组里面一定含有你要查找的数据）。。。。
那么为了加快查找速度，我们可以先拿头与尾中间的那个数据，与所要查找的数据（下面用c来表示该数据）进行比较，中间那个数的位置就在mid=(top+bot)/2。。。。
举这样的例子吧，从1到100的数中查找c。。。。
如果中间数50等于c，那就可以直接得出它在数组中的位置了，就是mid，代码if(c==a[mid])的作用就是这样。。。。
要说明一下，为什么它显示的代码printf("the position is %d\n",mid+1)中，mid要加1，如一个数在数组中的位置为0，那它就是在第一位，这个应该好理解吧。。。。
接着，如果中间数50小于c，那就说明了c的位置应该在中间到末尾那个位置，也就是51到100那个位置，代码if(c>a[mid])就是这样的意思，比较后，就把top=mid+1，即a[top]=51，再从51至100里面寻找c。。。。
如果中间数50大于c，那就表示c的位置应该在头到中间那个位置，就是说在1到49那个位置，对吧，代码中最后那个else起这样的作用，把bot=mid-1，也就是说a[bot]=49，通过循环，再从1至49里面寻找c。。。。
其实折半查找的思想很简单，就是比较中间数与查找数，判断出查找数是在前半段，还是在后半段，还是就等于中间数，如果在前半段，拿把前半段分离出来，再用其中间数与查找数比较，就这样不断循环，最终找到结果为止。。。。
数组若很大，如有1000个数，一个个进行比较的话，最差也得比较1000次，这样很耗费时间与资源，折半查找法就能比较好地减少了循环的次数。。。。
当然，前提是数组要预排序，如果是乱序的话，是不能用折半的。。。。
若还有什么不清楚，可以密我。。。。
折半查找，你要先确定一个头和一个尾，就像上面的top与bot，而你要查找的数据肯定会在头与尾之间那段数组中（前提是数组里面一定含有你要查找的数据）。。。。
那么为了加快查找速度，我们可以先拿头与尾中间的那个数据，与所要查找的数据（下面用c来表示该数据）进行比较，中间那个数的位置就在mid=(top+bot)/2。。。。
举这样的例子吧，从1到100的数中查找c。。。。
如果中间数50等于c，那就可以直接得出它在数组中的位置了，就是mid，代码if(c==a[mid])的作用就是这样。。。。
要说明一下，为什么它显示的代码printf("the position is %d\n",mid+1)中，mid要加1，如一个数在数组中的位置为0，那它就是在第一位，这个应该好理解吧。。。。
接着，如果中间数50小于c，那就说明了c的位置应该在中间到末尾那个位置，也就是51到100那个位置，代码if(c>a[mid])就是这样的意思，比较后，就把top=mid+1，即a[top]=51，再从51至100里面寻找c。。。。
如果中间数50大于c，那就表示c的位置应该在头到中间那个位置，就是说在1到49那个位置，对吧，代码中最后那个else起这样的作用，把bot=mid-1，也就是说a[bot]=49，通过循环，再从1至49里面寻找c。。。。
其实折半查找的思想很简单，就是比较中间数与查找数，判断出查找数是在前半段，还是在后半段，还是就等于中间数，如果在前半段，拿把前半段分离出来，再用其中间数与查找数比较，就这样不断循环，最终找到结果为止。。。。
数组若很大，如有1000个数，一个个进行比较的话，最差也得比较1000次，这样很耗费时间与资源，折半查找法就能比较好地减少了循环的次数。。。。
当然，前提是数组要预排序，如果是乱序的话，是不能用折半的。。。。
若还有什么不清楚，可以密我。。。。
温馨提示：答案为网友推荐，仅供参考
第1个回答 2010-07-12
备注：字母也有大小之分。
先说一下算法的基本思想：
在一个递增的数组中，如果要查找的数，比数组中间的数小，那么它肯定<中间以后所有的数，所以中间以后的数不可能有他，就不用查找。前半部分则又是一个序列，利用样的思想继续分成一半，直到查到 或 是结束没有这个数。
下面对程序进行注释：
#include<stdio.h>
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;top<=bot;) \\初始整个查找空间为整个数组，赋上下限初值，构成查找循环，循环条件是下限上于等于上限。
{
mid=(top+bot)/2; \\中间。
if (c==a[mid]) \\如果中间的数等于要查找的数，则查找成功。
{
printf("the position is %d\n",mid+1);\\因为数组从0开始，位置+1。
break;
}
else if (c>a[mid]) top=mid+1; \\如果中间的数不等，则缩小一半查找区间。如果是在后半区间，则下限top移动到中间数的后一个（MID比较过了所以移动mid+1）。
else bot=mid-1; \\如果在前半区间，则上限移动到MID的前一个。
}
if (top>bot) printf ("**\n"); \\如果失败，输出**
}本回答被提问者采纳
先说一下算法的基本思想：
在一个递增的数组中，如果要查找的数，比数组中间的数小，那么它肯定<中间以后所有的数，所以中间以后的数不可能有他，就不用查找。前半部分则又是一个序列，利用样的思想继续分成一半，直到查到 或 是结束没有这个数。
下面对程序进行注释：
#include<stdio.h>
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;top<=bot;) \\初始整个查找空间为整个数组，赋上下限初值，构成查找循环，循环条件是下限上于等于上限。
{
mid=(top+bot)/2; \\中间。
if (c==a[mid]) \\如果中间的数等于要查找的数，则查找成功。
{
printf("the position is %d\n",mid+1);\\因为数组从0开始，位置+1。
break;
}
else if (c>a[mid]) top=mid+1; \\如果中间的数不等，则缩小一半查找区间。如果是在后半区间，则下限top移动到中间数的后一个（MID比较过了所以移动mid+1）。
else bot=mid-1; \\如果在前半区间，则上限移动到MID的前一个。
}
if (top>bot) printf ("**\n"); \\如果失败，输出**
}本回答被提问者采纳
第2个回答 2010-07-13
折半查找法，是对应已经排序的数组查找某个特定数的方法。
以你给的题为例。一开始知道 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
以你给的题为例。一开始知道 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
第3个回答 2010-07-12
举个简单的例子吧，猜大小（幸福52那种），如果是0~100；
你肯定先猜50，如果大了，你就猜25，如果小了，就猜37（25+25/2）。。。以此类推，明白原理了吧，这样的速度是很快的
你肯定先猜50，如果大了，你就猜25，如果小了，就猜37（25+25/2）。。。以此类推，明白原理了吧，这样的速度是很快的
