数据结构(53) 顺序查找、二分查找、分块查找（索引顺序查找）

目录

1、顺序查找

1.1、一般线性表的顺序查找

1.2、有序表的顺序查找

2、折半查找

3、分块查找

---

1、顺序查找

顺序查找又称线性查找，主要用于在线性表中进行查找。顺序查找通常分为对一般的无序线性表的顺序查找和对按关键字有序的顺序表的顺序查找。下面分别进行讨论。

1.1、一般线性表的顺序查找

作为一种最直观的查找方法，其基本思想是从线性表的一端开始，逐个检查关键字是否满足给定的条件。若查找到某个元素的关键字满足给定条件，则查找成功，返回该元素在线性表中的位置；若已经查找到表另一端，但还没有查找到符合给定条件的元素，则返回查找失败的信息。下面给出其算法，主要是为了说明其中引入的“哨兵”的作用。

typedef struct
{
    ElemType *elem;    //元素存储空间基址，建表时按实际长度分配，0号单元留空
    int TableLen;      //表的长度
}SSTable;
 
int Search_Seq(SSTable ST,ElemType key)
{
    ST.elem[0] = key;   //哨兵
    for(i = ST.TableLen; ST.elem[i] != key;--i);  //从后往前找
    return i;
}

在上述算法中，将ST.elem[0]称为“哨兵”。引入它的目的是使得Search_Seq内的循环不必判断数据是否会越界，因为满足i==0时，循环一定会跳出。

对于有n个元素的表，给定值key与表中第i个元素相等，即定位第i个元素时，需进行n-i+1次关键字的比较，即Ci=n-i+1.查找成功时，顺序查找的平均长度为

 当每个元素的查找概率相同，即Pi=1/n时，有

查找不成功时，与表中各关键字的比较次数均为n+1次，从而顺序查找不成功的平均查找长度为ASL=n+1.

通常，查找表中记录的查找概率并不相等，若能预先得知每个记录的查找概率，则应先对记录的查找概率进行排序，使表中记录按查找概率由小到大重新排列。

综上所述，顺序查找的缺点是当n比较大的时候，平均查找长度较大，效率低；优点是对数据元素的存储没有要求，顺序存储或链式存储皆可。对表中记录的有序性也没有要求，无论记录是否按关键字有序，均可应用。当然了，线性的链表只能顺序查找

1.2、有序表的顺序查找

若在查找之前就已经知道表是关键字有序的免责查找失败时可以不用再比较到表的另一端就能返回查找失败的信息，从而降低顺序查找失败的平均查找长度。

假设表L是按关键字从小到大排列的，查找的顺序是从前往后，待查找元素的关键字为key，当查找到第i个元素时，发现第i个元素对应的关键字小于key，但第i+1个元素对应的关键字大于key，这时就可返回查找失败的信息，因为第i个元素之后的元素的关键字均大于key，所以表中不存在关键字为key的元素。

如下图所示

在有序表的顺序查找中，查找成功的平均查找长度和一般线性表的顺序长度一样。查找失败时，查找指针一定走到了某个失败结点。这些失败结点是我们虚构的空结点，实际上是不存在的，所以到达失败结点时所查找的长度等于它上面的一个圆形结点所在层数。查找不成功的平均查找长度在查找概率相同的情况下为：

式中，qj是到达第j个失败结点的概率，在相同查找概率的情况下，它为1/(n+1)；lj是第j个失败结点所在的层数。当n=6时，结构为3.86，比一般的顺序查找算法好一些。

2、折半查找

折半查找又称为二分查找，它仅适用于有序的顺序表。

折半查找的基本思想：受限将给定值key与表中中间位置的元素比较，若相等，则查找成功，返回该元素的存储位置；若不等，则所需查找的元素只能在中间元素以外的前半部分或后半部分（例如，在查找表升序排列时，若给定值key大于中间元素，则所查找的元素只可能在后半部分）。然后在缩小的范围内继续进行同样的查找，如此重复，直到找到位置，或确定表汇总没有所需要查找的元素，则查找不成功，返回查找失败的信息。算法如下：

int Binary_Search(SeqList L,ElemType key)
{
    int low = 0,high = L.TableLen -1,mid;
    while(low <= high)
    {
        mid = (low+high)/2;
        if(L.elem[mid] == key)
            return mid;
        else if(L.elem[mid] > key)
            high = mid-1;
        else if(L.elem[mid] < key)
            low= mid+1;
    }
    return -1;
}

树中每个圆形结点表示一个记录，结点中的值为该记录的关键字；树中最下面的叶节点都是方形的，它表示查找不成功的情况。从判定树可以看出，查找成功时的查找长度为从根节点到目的结点的路径上的结点数，而查找不成功时查找长度为从根节点到对应失败结点的父结点的路径上的结点数；每个结点值均大于其左子结点值，且均小于其右子结点值。若有序序列有n个元素，则其对应的判定树有n个圆形的非叶结点和n+1个方形的叶节点。

折半查找的过程可用上图所示的二叉树来描述，称为判定树。显然判定树是一棵平衡二叉树。

用折半查找法查找到给定值的比较次数最多不会超过树的高度。在等概率查找时，查找成功的平均查找长度为

 式中，h是树的高度，并且元素个数为n时树高。所以，折半查找的时间复杂度为，平均情况下比顺序查找的效率高。

3、分块查找

分块查找又称索引顺序查找，它吸取了顺序查找和折半查找各自的优点，即有动态结构，又适于快速查找。

分块查找的基本思想：将查找表分为若干子块。块内的元素可以无序，但块之间是有序的，即第一个块中的最大关键字小于第二块中所有记录的关键字，第二个块中的最大关键字小于第三个块中的所有记录的关键字，以此类推。再建立一个索引表，索引表中的每个元素含有各块的最大关键字和各块中的第一个元素的地址。索引表按关键字有序排列。

分块查找的过程分为两步：第一步是在索引表中确定待查记录所在块，可以顺序查找或者二分查找索引表；第二部是在块内顺序查找。

例如，关键码集合为{88,24,72,61,21,6,32,11,8,31,22,83,78,54}，按照关键码值24,54,78,88分为四个块和索引表。

分块查找的平均查找长度为索引查找和块内查找的平均长度之和。设索引查找和块内查找的平均长度分别为Ll,Ls,则分块查找的平均查找长度为：

将长度为n的查找表均匀地分为b块，每块有s个记录，在等概率情况下，若在块内和索引表中均采用顺序查找，则平均查找长度为

若队索引表采用折半查找时，则平均查找长度为