(39)--程序案例-折半查找初识C语言.pdf

《(39)--程序案例-折半查找初识C语言.pdf》由会员分享，可在线阅读，更多相关《(39)--程序案例-折半查找初识C语言.pdf（4页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、【案例】在利用一维数组存储的一个升序数列中，使用折半查找法查找指定数值。1问题分析与算法设计 查找是在一组数据中找指定的值。不同的数据对象，有不同的查找方法。数据存储的结构不同，查找的方法也不同。为便于理解题意，先对查找的方法进行简要说明。对于给定的一组数，查找 x 的方法有多种，最简单的方法是顺序查找，就是从头开始依次与 x 进行比较，找到 x 时查找成功，查找过程结束；全部数据查找一遍，未找到 x，则查找失败，查找过程结束。顺序查找方法简单，但效率低。折半查找是一种高效的查找方法，它须在一个有序的数列中进行，具体方法如下。设有 N 个数据的数列已升序排序，存储在长度为 N 的一维数组 a

2、中，对在查找范围内的数据设置 3 个特殊点，首位置为 top，末位置为 bot，中间位置为mid=(top+bot)/2。查找初始，top 为数组首元素的下标值 0，bot 为数组末元素的下标值 N-1，mid 为中间位置元素的下标值(N-1)/2。以下为查找过程：比较 x 与 amid，若 x 与 amid相等，则查找成功，查找过程结束；否则，若 xamid，则 top=mid+1；若 xbot，则查找失败，查找过程结束；否则，mid=(bot+top)/2，转。图示是在数列3,6,7,8,21,23,36,38,67,69,80,82,85,88,96中查找 69 时，top、bot、mi

3、d 的变化情况。该查找过程经过三次之后结束，查找成功。图示中的、是对三次查找所做的标识，表中列出了查找过程中各项数据的动态变化情况。63968885828069673836232187topmidbotmidmidbotbottoptop111222333a1a0a14a13a12a11a10a9a8a7a6a5a4a3a2 表：折半查找过程动态信息表 查找过程 本次查找范围及中间位置 本次查找结果 下一次查找范围 top bot mid 第 1 次 0 14 7 amidx 在mid之前，bot=mid-1 第 3 次 8 10 9 amid=x 查找结束 上述查找过程的算法 N-S 图如图

4、所示。将N个数的升序数列保存到数组a中top=0,bot=N-1mid=(top+bot)/2ifelse ifelseamid=xamidx查找成功breaktop=mid+1x若存在，则在mid之后bot=mid-1x若存在，则在mid之前while(top=bot)bottop是否输出找不到信息输出找到信息 2实现程序#include#define N 15 int main()int aN=3,6,7,8,21,23,36,38,67,69,80,82,85,88,96;int x,top,bot,mid;printf(Input x:);scanf(%d,&x);/*输入要查找的数值*/top=0;/*设置初始查找边界*/bot=N-1;do mid=(top+bot)/2;/*确定中间位置*/if(amid=x)break;/*找到 x 后终止循环*/else if(amidx)top=mid+1;/*确定后半段为下一次查找的范围*/else bot=mid-1;/*确定前半段为下一次查找的范围*/while(top=bot);if(bottop)/*只有 x 不存在时，bottop 才会成立*/printf(%d:no found.n,x);else printf(Success!a%d is%d.n,mid,x);return 0;