1.静态查找表概述

查找是集合类型的数据结构最基本的操作，通常将用于查找的集合称为查找表。

1.1.静态查找表的定义

如果查找表中的数据元素个数和每个数据元素的值是不变的，这样的查找表称为静态查找表。

如果一个查找表不仅要支持查找操作，还支持插入和删除操作，查找表是动态变化的，表中数据元素个数不是固定的，这样的表称为动态查找表。

给定某个数据元素关键字X和一个集合S，返回关键字为X的数据元素在集合S中的位置或一个不存在的标志。如果X出现不止一次，返回出现位置中的任意一个，集合S是不变的。这样的操作就是静态表的查找。

最简单的场景就是字典，比如在新华字典中查找某个汉字。

集合中的元素是无需的时候，就只能做线性的顺序查找。

顺序查找就是遍历集合中的所有元素，直到找到匹配的为止。

此种场景时间复杂度为O(N)

有序表的查找有以下四种方式。

有序表的顺序查找与无序表的顺序查找类似。只不过顺序查找可以提前结束，无需遍历整个表。而无序表的查找如果找不到元素，则会遍历整个表。

例如，在以下有序表中查找8，则查找到第5个元素（结点9）时，可退出后续的查找，查找过程进行了5次比较。

而在无序表中，要查找8，则需要遍历完整个数组，进行8次比较。

有序表的顺序查找时间复杂度还是O(N)。

当查找的集合很大时，顺序查找的时间会很长。

二分查找是指，每次检查集合中间的那个元素。如果中间元素等于要查找的元素，则查找完成。如果确定要查找的元素在中间值的前半部分或后半部分，则缩小范围，在前半部分或后半部分进行查找。

二分查找的时间复杂度为O(logN)。

当查找范围很小时，二分查找递归进展缓慢，每次只能消除少量的元素。

所以，现实查找场景经常采用混合查找的策略——查找范围较大时，采用二分查找；当缩小到一定范围后，则采用顺序查找。

插值查找与二分查找类似，只不过确定查找位置时有差异。二分查找采用中间结点，将整个集合均匀分为两部分。而插值查找根据以下算法确定查找位置

现实生活中不太会用插值查找，实现比二分查找复杂，只适应特殊场景。

分块查找也称为索引顺序块的查找。

把整个有序表分成若干块，块内的元素可以是有序的，也可以是无序的，但块之间必须是有序的。

分块查找由两个阶段组成：查找索引和查找块。先查找索引表，找到数据所在的块，由于索引表是有序的，可以采用顺序查找或二分查找。然后块内查找，如果块内是有序的，可以采用二分查找，如果块是无序的，只能采用顺序查找。