C语言程序设计基础：数组查找方法

2023-11-20 理论教育版权反馈

【摘要】：若在表中找不到与给定条件相符合的数据，则称为不成功的查找，给出提示信息或空位置信息。本节介绍最常用的两种查找方法：顺序查找和折半查找。③基准位置数据值与查找的关键字值不相符时，在两个子集合中选取一个，重复执行①、②，直到被处理的查找集合中没有数据为止。图6.11是在一有序序列中实现对key＝21进行折半查找的过程。

查找也称为检索，是在一个数据集合中找出符合某种条件的数据。查找的结果有两种：在数据集合中找到了与给定条件相符合的数据，称为成功的查找，根据需要可以处理所查找的数据信息或给出数据的位置信息。若在表中找不到与给定条件相符合的数据，则称为不成功的查找，给出提示信息或空位置信息。本节介绍最常用的两种查找方法：顺序查找和折半查找。

1.顺序查找（Linear search）

顺序查找又称为线性查找。其基本过程是：从待查集合中的第一个数据开始，将给定的关键字值与查找集合中的数据逐个进行比较。如果找到相符合的数据时，查找成功；如果在数据集合中找不到与关键字值相符合的数据，则查找失败。顺序查找方法适用于被查找集合无序的场合。

【例6.21】　编写程序实现顺序查找算法，在随机生成的50个整数中查找指定值，要求程序能够显示出查找是否成功的信息。

2.折半查找（Binary search）

折半查找法又称为二分查找法，该算法要求在一个对查找关键字而言有序的数据序列上进行，其基本思想是逐步缩小查找目标可能存在的范围，具体描述如下：

①以查找集合中间位置的数据作为基准，将查找集合划分为两个子集。

②基准位置数据值与查找的关键字值相符合时，返回基准数据的位置，算法结束。

③基准位置数据值与查找的关键字值不相符时，在两个子集合中选取一个，重复执行①、②，直到被处理的查找集合中没有数据为止。

图6.11是在一有序序列中实现对key＝21进行折半查找的过程。(www.chuimin.cn)

图6.11　折半查找算法示意图

【例6.22】　编写程序实现折半查找算法，在随机生成的50个整数中查找指定值，要求程序能够显示出查找是否成功的信息。