查找

查找的基本概念

列表：由同一类型的元素（或记录）构成的集合，可以用任意数据结构表示。

关键字：数据元素某个数据项的值，用关键字可以标示列表中的一个或一组数据元素。如果一个关键字只能对应列表中的唯一一个数据元素，那么它就是主关键字（就像函数，一个自变量的值只对应一个因变量的值），否则它就是次关键字。（简单的来说，就是某一个对象的特征，比如说，GDP排名，行政区域的级别都是关键字，每个GDP排名只对应一个城市，它是主关键字，行政区域为直辖市的不止一个城市，所以它是次关键字）

查找：根据给定的关键字值，在特定列表中确定一个关键字值与给定的相同的数据元素，若存在，则返回该数据元素在列表中的位置，若不存在，返回空地址和查找失败信息，并可根据要求插入这个不存在的数据元素。

查找算法有三类参量（三个要素）：查找对象K（要找什么），查找范围L（在哪里找），查找结果（K在L中的位置）

静态查找：只对数据元素进行查找

动态查找：查找的同时插入找不到的元素，或从表中删除查找到的元素，即允许元素进行变化。

查找的基本方法分为两大类：比较式查找法和计算式查找法。

比较式查找法：对列表中的数据元素的关键字进行比较，查找关键字相同的数据元素。（比如说，在拼拼图的时候，就是对拼图碎片的形状和图案进行比较）它还能再分为基于线性表的查找法和基于树的查找法。

计算式查找法：通过计算来得到数据元素的存储地址。一般来说，计算式查找法所需的存储空间比比较式查找法大，而查找速度更快。所以这通常是一种牺牲空间来换取时间的方法。（比如说字典，在编写字典时，将所有汉字按部首进行排序，这是一个构造哈希表的过程，许多汉字放在同一页相当于使用链地址法解决冲突；在查找某一个汉字时，我们根据部首可以得到汉字所在的页码，相当于直接根据数据元素的关键字查找到了地址）

基于线性表的查找法

顺序查找法

顺序查找法的特点：对线性表中的各个元素与逐个进行比较，直到成功或失败。

因为顺序查找法是在线性表中查找的，所以通常是在顺序结构或者链式结构中查找。

例：设置监哨站和不设置

我们需要一种方法来衡量这个查找方法的快慢，也就是这个查找算法的性能。因此这边引入了平均查找长度。

平均查找长度：简单来说，就是在特定列表中进行查找时，需要进行比较的次数的期望。

其中是查找列表中第个元素的概率，是指查找到第个元素时，已经进行过的关键字比较次数。

注：这并不意味着计算式查找一定为0。

顺序查找法查找成功时，每个数据元素被查找的概率为，而查找到第个数据时，已经查找了次。

#card=math&code=ASL%7Bsucc%7D%3D%5Csum%5Climits%7Bi%3D1%7D%5E%7Bn%7D%5Cfrac%7Bi%7D%7Bn%7D%3D%5Cfrac%7B1%7D%7B2%7D%28n%2B1%29)

查找失败时，查找的算法历遍所有的数据元素，因为我们在表的一端设置了一个监哨站，所以表的长度实际上变为。

顺序查找法可以通过设置监哨站，省去检查是否越界的步骤，以此提高查找效率。

折半查找法

折半查找法对列表有两个要求：

1、必须采用顺序存储结构（因为折半的时候需要计算中间位置的地址）

2、必须按关键字大小有序排列（通过和中间位置的元素的关键字值大小进行比较来确定是在哪一个部分中）

把折半查找中，中间项作为根，中间项前的子表作为左子树，中间项后的作为右子树，这样就可以构造出折半查找过程的一棵二叉树。

为了便于计算，假设这是一棵满二叉树

-1%5Capprox%20log_2(n%2B1)-1#card=math&code=ASL%3D%5Cfrac%7Bn%2B1%7D%7Bn%7Dlog_2%28n%2B1%29-1%5Capprox%20log_2%28n%2B1%29-1)

分块查找法

列表必须组织成两种索引顺序结构。

1、列表分成若干个子块。一般情况下，块的长度均匀，最后一块可以不满。每块中的元素是可以任意排列的。

2、构造一个索引表，每个索引项对应每一个块的起始位置，并存储每一块中的最大关键字或者最小关键字。

注意，块与块之间，索引项之间必须有序排列（举例）

这样便能方便地确定在哪一块中。

分块查找分为查找索引表和查找块两个步骤。可以分别对应前两种查找方法。

其中指在索引表中的平均查找长度，指在对应的块中的平均查找长度。

我们假设表长度为，分成块，因此每块中有个元素。

如果都用顺序查找法，则

%2B1#card=math&code=ASL_%7Bbs%7D%3D%5Cfrac%7Bb%2B1%7D%7B2%7D%2B%5Cfrac%7Bs%2B1%7D%7B2%7D%3D%5Cfrac%7Bb%2Bs%7D%7B2%7D%2B1%3D%5Cfrac%7B1%7D%7B2%7D%28%5Cfrac%7Bn%7D%7Bs%7D%2Bs%29%2B1)

如果在索引表中使用使用折半查找法，则

-1%2B%5Cfrac%7Bs%2B1%7D%7B2%7D%5Capprox%20log2(%5Cfrac%7Bn%7D%7Bs%7D%2B1)%2B%5Cfrac%7Bs%7D%7B2%7D#card=math&code=ASL%7Bbs%7D%3Dlog_2%28b%2B1%29-1%2B%5Cfrac%7Bs%2B1%7D%7B2%7D%5Capprox%20log_2%28%5Cfrac%7Bn%7D%7Bs%7D%2B1%29%2B%5Cfrac%7Bs%7D%7B2%7D)