对分查找_查找方法 - 威林百科weilinceramic.com

对分查找

查找方法

对分查找是一种效率很高的查找方法，但被查找的数据必须是有序（例如非递减有序）的。

前提

对分查找的前提是待查找的数据必须是有序的。

原理

对分查找首先将查找键与有序数组内处于中间位置的元素进行比较，如果中间位置上的元素内的数值与查找键不同，根据数组元素的有序性，就可确定应该在数组的前半部分还是后半部分继续进行查找；在新确定的范围内，继续按上述方法进行查找，直到获得最终结果。

在数组中的数据是有序的，如果是增序的，是指下标越小的数组元素中存储的数据也越小，减序则相反。设数组变量d中存储了n个互不相同的数据，则数组变量d中的数据是增序时，有：

d(1)＜d(2)＜…d(i)＜d(i+1)＜…＜d(n-1)＜d(n)

优势

由于对分查找每查找一次，查找范围就缩小一半，因此效率要远高于顺序查找。

流程图

对分查找的程序流程图（略图）

参考资料

最新修订时间：2023-10-28 11:21

条目作者

概述

前提

原理

优势

参考资料