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

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

时间：2021-08-29 19:44:17

#笔记整理

查找

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

基本概念

查找表

由同一类型的数据元素（记录）构成的集合。

查找的定义

给定一个值 key，在含有 n 个记录的表中找出关键字等于 key 的记录。若找到，则查找成功，返回该记录的信息或该记录在表中的位置；否则查找失败，返回相关的指示信息。

静态查找表(Static Search Table)——基于线性表的查找法

查询某个特定的元素是否在表中；检索某个特定的元素的各种属性。

即：只作查找操作的查找表。

动态查找表(Dynamic Search Table)——基于树表的查找法

若在查找的同时对表做修改运算(如插入和删除)。

即在查找过程中同时插入查找表中不存在的数据元素，或删除某个已存在的数据元素。

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

次关键字：能标识多个记录的关键字。

平均查找长度 ASL(Average Search Length) ：

为确定数据元素在查找表中的位置，需和给定值进行比较的关键字个数的期望值，称为查找算法在查找成功时的平均查找长度。

静态查找表

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

顺序查找折半查找（二分查找）索引顺序表查找（分块查找）

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

1. 顺序查找（sequential search）

又叫线性查找，是最基本的查找技术，它的查找过程是：

从表中第一个（或最后一个）记录开始，逐个进行记录的关键字和给定值比较，若某个记录的关键字和给定值相等，则查找成功；如果直到最后一个（或第一个）记录，其关键字和给定值比较都不等时，则表中没有所查的记录，查找不成功。

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

折半查找的思想：

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

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

判定树(比较树)

折半查找过程可用二叉树来描述，把当前查找区间的中间位置上的记录作为根，左子表和右子表的中间位置的记录分别作为根的左子树和右子树，这样形成的树称为折半查找判定树（比较树）。

折半查找效率分析

如果查找表中有 n 个元素，查找成功和失败的平均查找长度与有 n 个结点的完全二叉树的高度相同。即：

示例：

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

插值查找法是根据要查找的关键字 Key 与查找表中最大最小记录的关键字比较后的查找方法。

前提：关键字值分布比较均匀。

思路：

折半查找的 midmidmid = low+high2{low + high} \over {2}2low+high = low + 12{1} \over {2}21 ∗(high−low)* (high - low)∗(high−low)，对 121 \over 221 进行优化之后，改为 (key−a[low])(a[high]−a[low])(key - a[low]) \over (a[high] - a[low])(a[high]−a[low])(key−a[low])。

即 midmidmid = lowlowlow + (key−a[low])(a[high]−a[low])(key - a[low]) \over (a[high] - a[low])(a[high]−a[low])(key−a[low]) ∗(high−low)* (high - low)∗(high−low)。

时间复杂度也为 O(logn)O(log n)O(logn)，但是在关键字分布较为均匀的情况下，平均性能比折半查找好。

算法实现示例：

// 在 nums 中寻找 target，若找到，返回目标所在的下标，否则返回 -1int 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地址