查找算法（I） 顺序查找 二分查找 索引查找

查找

本文为查找算法的第一部分内容，包括了基本概念，顺序查找、二分查找和索引查找。关于散列表和B树查找的内容，待有空更新吧。

基本概念

查找（search）又称检索，在计算机上对数据表进行查找，就是根据所给条件查找出满足条件的第一条记录（元素）或全部记录。

若没有找到满足条件的记录，则返回特定值，表明查找失败；若查找到满足条件的 第一条记录，则表明查找成功，通常要求返回该记录的存储位置或记录值本身，以便进行进一步处理；若需要查找到满足条件的所有记录，则可看做在多个区间内连 续查找到满足条件的第一条记录的过程，即首先在整个区间内查找到满足条件的第一条记录，接着在剩余的区间内查找满足条件的第一条记录，以此类推，直到剩余 区间为空为止。

作为查找对象的表的结构不同，其查找方法一般也不同。

查找过程是关键字比较的过程，比较次数的多少就是相应算法的时间复杂度，它是衡量一个查找算法优劣的重要指标。

对于一个查找算法的时间复杂度，还可以采用平均查找长度（Average Search Length, ASL），即在查找成功情况下的平均比较次数来表示。

平均查找长度的计算公式为：ASL=∑p_ici

其中n为查找表的长度，即表中所含元素的个数，p_i 为查找第i个元素的概率， c_i为查找第i个元素时所需的比较次数。

若查找每个元素的概率相同，在具有n个元素的线性表上顺序查找其关键字域的值等于K的元素时，c_i=i ，所以平均查找长度为: ASL=(n+1)/2

顺序表查找

顺序表（sequential list）是指集合或线性表的顺序存储结构。

在顺序表上进行查找主要有两种方法：顺序查找方法和二分查找方法。

顺序查找

顺序查找（sequential search）又称线性查找，从顺序表的一端开始，依次将每个元素的关键字同给定值K进行比较，若某个元素的关键字等于K，则表明查找成功，返回该元素下标，若所有元素都比较完毕仍找不到，则表明查找失败，返回特定值，常用-1.

优点：最简单，对元素排列次序无要求，插入新元素方便。

缺点：速度慢，平均查找长度为（n+1）/2，约为表长度一半。

提高效率的方法：按查找概率从大到小排列。事先未知概率的情况下，每次查找到一个元素时，将它与前驱元素对调位置，这样，查找频度高的元素就会逐渐前移。

二分查找

二分查找（binary search）又称折半查找，对分查找。作为二分查找对象的数据表必须是顺序存储的有序表。

二分查找的过程：有序表A[0]~A[n-1]，首先取中点元素A[mid] 的关键字同给定值K进行比较，若相等则查找成功；否则，若K< A[mid].key，则在左子表中继续进行二分查找；若K> A[mid].key，则在右子表中继续进行二分查找；这样，经过一次比较，就缩小一半查找空间，如此进行下去，直到查找成功，或者当前查找区间为空时为 止（或区间的下界大于等于上界时为止）。

二分查找的过程是递归的，也很容易写成非递归算法，只需要根据情况修改待查找区域的上下界即可。

二分查找过程可用一棵二叉树来描述，树中的每个根结点对应当前查找区间的中点元素，它的左子树和右子树分别对应该区间的左子表和右子表，通常把此树称为二分查找的判定树。由于二分查找在有序表上进行，所以其对应的判定树是一棵二叉搜索树（排序树）。

在有序表上二分查找一个关键字等于K的元素时，对应着判定树中从根结点到待查结点的一条路径，同关键字进行比较的次数就等于该路径上的结点数，或者说等于待查结点的层数。

优点：时间复杂度为O(logn)，查找速度快。

缺点：需要建立有序表，并且插入和删除会比较麻烦。另外，只适用于顺序存储的有序表，不适用于链接存储的有序表。

索引查找

索引的概念

索引查找（index search）又称分级查找。

比如在查字典的时候，首先在部首表中查到对应检字表中的页码，再在检字表中根据字的笔画数查到对应正文中的页码，最后在此页码中找到待查的汉字。其中，整个字典就是索引查找的对象，字典正文称为主表，部首表、检字表都是为方便查找主表而建立的索引，所以被称为索引表。

检字表以主表作为查找对象，所以称检字表为一级索引，称部首表为二级索引，即对一级索引的索引。

在计算机中，索引查找是在集合或线性表的索引存储结构的基础上进行的。索引存储的基本思想是：首先把主表按照一定的关系划分成若干个子表，为每个子表建立一个索引项，由所有的这些索引项构成主表的一个索引表，然后，可以采用顺序或者链接的方式来存储索引表和每个子表。

索引表中的每个索引项通常包含三个域（至少包含前两个域）：一是索引值域（index），用来存储标识对应子表的索引值，相当于记录的关键字；二是子表的开始位置域（start），用来存储对应子表的第一个元素的存储位置；三是子表长度域（length），用来存储对应子表的元素个数。

在索引存储中，若索引表中的每个索引项对应多条记录，则称为稀疏索引；若每个索引项唯一对应一条记录，则称为稠密索引。

索引查找算法

索引查找是在索引表和主表上进行的查找。

首先根据给定的索引值K1，在索引表上查找出索引值等于K1的索引项，以确定对应子表在主表中的开始位置和长度，然后再根据给定的关键字K2，在对应的子表中查找出关键字等于K2的元素。

索引查找的比较次数等于算法中查找索引表的比较次数和查找相应子表的比较次数之和。（下面的讨论只考虑包含一级索引的情况）。

假定索引表长度为m，相应子表长度为s，则索引查找的平均查找长度为：

ASL =(1+m)/2+ (1+s)/2 = 1+ (m + s)/2

因为所有子表的长度之和等于主表长度n，所以若每个子表长度相同，即s=n/m，则平均查找长度为ASL =1+ (m + n/m)/2 。

由数学知识，当m=n/m时，平均长度最小，即 ASL= 1+n^½。

可见，索引查找的速度快于顺序查找，但低于二分查找。在主表被分为n^½ 个子表的前提下，其时间复杂度为O(n^½) 。

分块查找

分块查找（blocking search）属于索引查找。它要求主表中每个子表（子表又称为块）之间是有序的（递增或递减）。

比如递增，即前块中的最大关键字必须小于后块中的最小关键字。但每个块中的元素排列次序可以是任意的。

它还要求索引表中的每个索引项的索引值域用来存储对应块中的最大关键字。

索引表是有序的，主表中的关键字域和索引表中的索引值域具有相同的数据类型，即为关键字所属的类型。

由于索引表是有序的，所以在索引表上既可采用顺序查找，又可采用二分查找，而每个块中的记录排列是任意的，所以在块内只能采用顺序查找。