顺序查找

顺序查找是一种最简单的查找方法。

思路：从表的一端开始，顺序扫描线性表，依次将扫描到的关键字和给定值k相比较，

若当前扫描到的关键字与k相等，则查找成功；若扫描结束后，仍未找到关键字等于k的记录，则查找失败。

顺序查找的算法如下（在顺序表R中查找关键字为k的元素，成功时返回找到的元素的逻辑序号，失败时返回0）：

从顺序查找过程可以看到（不考虑越界比较in），ci取决于所查记录在表中的位置。

如查找表中第1个记录R时,仅需比较一次；而查找表中最后一个记录R时，需比较n次，即ci=i。因此,成功时的顺序查找的平均查找长度如图

二分查找

二分查找也称为折半查找，要求线性表中的节点必须己按关键字值的递增或递减顺序排列，即有序表。

思路：首先用要查找的关键字k与中间位置的节点的关键字相比较，这个中间节点把线性表分成了两个子表。

若比较结果相等则查找完成;若不相等，再根据k与该中间节点关键字的比较大小确定下一步查找哪个子表，这样递归进行下去，直到找到满足条件的节点或者该线性表中没有这样的节点。

其算法如下（在有序表R中进行折半查找，成功时返回元素的逻辑序号，失败时返回0）：

二分查找过程可用二叉树来描述，称为描述二分查找的判定树或比较树。

方法：把当前查找区间的中间位置上的记录作为根；左子表和右子表中的记录分别作为根的左子树和右子树。

分块查找：介于顺序查找和二分查找之间的查找方法

采用二分查找索引表的分块查找算法如下

若以二分查找来确定块，则分块查找成功时的平均查找长度为：

不会的小伙伴可以给小编投票留言