【数据结构】查找：基本概念及静态查找表（顺序查找、二分查找、索引查找）

偏执的太偏执、 2021-10-29 06:42 457阅读 0赞

\#笔记整理  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9zdGV2ZS5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70]

# 查找 #

*  **[查找的基本概念][Link 1]**
 *  **[静态查找表——基于线性表的查找法（二分查找）][Link 1]**
 *  **[动态查找表——基于树表的查找法（二叉排序树、平衡二叉树][Link 2][、B树、红黑树）][B]**
 *  **[哈希表——计算式查找法][Link 3]**

## 基本概念 ##

**查找表**  
由同一类型的数据元素（记录）构成的集合。  
**查找的定义**  
给定一个值 key，在含有 n 个记录的表中找出关键字等于 key 的记录。若找到，则查找成功，返回该记录的信息或该记录在表中的位置；否则查找失败，返回相关的指示信息。

**静态查找表(Static Search Table)——基于线性表的查找法**  
查询某个特定的元素是否在表中；检索某个特定的元素的各种属性。  
即：只作查找操作的查找表。

**动态查找表(Dynamic Search Table)——基于树表的查找法**  
若在查找的同时对表做修改运算(如插入和删除)。  
即在查找过程中同时插入查找表中不存在的数据元素，或删除某个已存在的数据元素。

**主关键字：** 能唯一标识一个记录的关键字。  
**次关键字：** 能标识多个记录的关键字。

**平均查找长度 ASL(Average Search Length) ：**  
为确定数据元素在查找表中的位置， 需和给定值进行比较的关键字个数的期望值，称为查找算法在查找成功时的平均查找长度。  
![在这里插入图片描述][20190820222149459.png]

### 静态查找表 ###

三种在线性表上进行查找的方法：

1.  顺序查找
2.  折半查找（二分查找）
3.  索引顺序表查找（分块查找）

因为不考虑在查找的同时对表做修改，故上述三种查找操作都是在静态查找表上实现的。

#### 1. 顺序查找（sequential search） ####

又叫线性查找，是最基本的查找技术，它的查找过程是：  
从表中第一个（或最后一个）记录开始，逐个进行记录的关键字和给定值比较，若某个记录的关键字和给定值相等，则查找成功；如果直到最后一个（或第一个）记录，其关键字和给定值比较都不等时，则表中没有所查的记录，查找不成功。

#### 2. 折半查找法 （binary search，二分查找法） ####

**折半查找的思想：**  
将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表， 如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。

要求待查找的表必须是按关键字大小有序排列的顺序表。

**判定树(比较树)**  
折半查找过程可用二叉树来描述，把当前查找区间的中间位置上的记录作为根，左子表和右子表的中间位置的记录分别作为根的左子树和右子树，这样形成的树称为折半查找判定树（比较树）。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9zdGV2ZS5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70 1]  
**折半查找效率分析**  
如果查找表中有 n 个元素，查找成功和失败的平均查找长度与有 n 个结点的完全二叉树的高度相同。即：  
![在这里插入图片描述][20190820222242992.png]  
**示例：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9zdGV2ZS5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70 2]

##### 折半查找的改进——插值查找法（interpolation search） #####

插值查找法是根据要查找的关键字 Key 与查找表中最大最小记录的关键字比较后的查找方法。  
**前提：** 关键字值分布比较均匀。  
**思路：**  
折半查找的  m i d mid mid =  l o w + h i g h 2 \{low + high\} \\over \{2\} 2low\+high = low +  1 2 \{1\} \\over \{2\} 21  ∗ ( h i g h − l o w ) \* (high - low) ∗(high−low)，对  1 2 1 \\over 2 21 进行优化之后，改为  ( k e y − a \[ l o w \] ) ( a \[ h i g h \] − a \[ l o w \] ) (key - a\[low\]) \\over (a\[high\] - a\[low\]) (a\[high\]−a\[low\])(key−a\[low\])。  
即  m i d mid mid =  l o w low low \+  ( k e y − a \[ l o w \] ) ( a \[ h i g h \] − a \[ l o w \] ) (key - a\[low\]) \\over (a\[high\] - a\[low\]) (a\[high\]−a\[low\])(key−a\[low\])  ∗ ( h i g h − l o w ) \* (high - low) ∗(high−low)。  
时间复杂度也为  O ( l o g n ) O(log n) O(logn)，但是在关键字分布较为均匀的情况下，平均性能比折半查找好。

算法实现示例：

// 在 nums 中寻找 target，若找到，返回目标所在的下标，否则返回 -1
    int binarySearch(vector<int> nums, int target){
        
        int len = nums.size();
        int low = 0;
        int high = len - 1;
        int mid;
        while(low <= high){
        
            mid = (low + high) / 2;   // 若 nums 中元素的值分布均匀，使用改进的插值查找法 mid = low + (target - nums[low]) / (nums[high] - nums[low]) * (high - low)
            if(target < nums[mid]){
        
                high = mid - 1;
            }else if(target > nums[mid]){
        
                low = mid + 1;
            }else{
        
                return mid;
            }
        }
        return -1;
    }

[github地址][github]

#### 索引顺序查找(分块查找) ####

分块查找法是一种性能介于顺序查找和折半查找之间的查找方法。  
**索引顺序查找的思想：**  
将表 \[1…n\] 均分为 b 块，前 b - 1 块中记录个数为 s = n/b，最后一块即第 b 块的记录数小于等于 s。  
表是“分块有序”的，即这些 b 块组成一个索引表，这个索引表是按照每一块的最大值对块进行递增排序，是一个递增有序表。

**示例：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9zdGV2ZS5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70 3]  
**索引顺序查找的效率分析：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9zdGV2ZS5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70 4]

### 静态查找表的三种查找方法比较 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9zdGV2ZS5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70 5]

**扩展：**

#### 稠密索引 ####

稠密索引是指在线性索引中，将数据集中的每个记录对应一个索引项。索引项按关键字进行有序排列。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9zdGV2ZS5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70 6]

#### 倒排索引 ####

不是由记录来确定属性值，而是由属性值来确定记录的位置，因而成为倒排索引。  
倒排索引源于实际应用中需要根据属性（或字段、次关键码）的值来查找记录。  
这种索引表中的每一项都包括一个属性值和具有该属性值的各记录的位置。  
![在这里插入图片描述][20190821112714880.png]![在这里插入图片描述][20190821112720583.png]  
上面的单词表就是一张索引表，索引项的通用结构是：  
• 次关键字，如上面的英文单词；  
• 记录号表，如上面的文章编号。  
其中记录号表存储具有相同次关键字的所有记录的记录号（可以是指向记录的指针或者是该记录的主关键字）。

参考资料：

1.  《数据结构（C语言版）》----严蔚敏
2.  《数据结构》课堂教学ppt ---- 刘立芳
3.  《数据结构算法与解析（STL版）》 ---- 高一凡
4.  《大话数据结构》 ---- 程杰
5.  《挑战程序设计竞赛2：算法和数据结构》 ---- 渡部有隆

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9zdGV2ZS5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70]: /images/20211029/ad965e6baaf6436588003f08ec01645e.png
[Link 1]: https://steve.blog.csdn.net/article/details/99890774
[Link 2]: https://steve.blog.csdn.net/article/details/99892860
[B]: https://steve.blog.csdn.net/article/details/99894294
[Link 3]: https://steve.blog.csdn.net/article/details/99958241
[20190820222149459.png]: /images/20211029/33c6aa23c0334e54ab103fb7e9efc43b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9zdGV2ZS5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70 1]: /images/20211029/821555c08fbc45be9a00ed9cd2ff6e32.png
[20190820222242992.png]: /images/20211029/6ef4832758c34eacaa133d1278a91013.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9zdGV2ZS5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70 2]: /images/20211029/6e6f6f77e0b6441db7b0203f1949b69b.png
[github]: https://github.com/yohstone/data-structure/blob/master/search.cpp
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9zdGV2ZS5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70 3]: /images/20211029/aaf3b39a133941e0baaa865915b86ee2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9zdGV2ZS5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20190820223157802.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9zdGV2ZS5ibG9nLmNzZG4ubmV0,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9zdGV2ZS5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20190820223243610.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9zdGV2ZS5ibG9nLmNzZG4ubmV0,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9zdGV2ZS5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/20190821112648417.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9zdGV2ZS5ibG9nLmNzZG4ubmV0,size_16,color_FFFFFF,t_70
[20190821112714880.png]: https://img-blog.csdnimg.cn/20190821112714880.png
[20190821112720583.png]: https://img-blog.csdnimg.cn/20190821112720583.png