【数据结构-查找】7.1顺序查找-折半查找-分块查找-平芜编程栈

【数据结构-查找篇】7.1 顺序查找、折半查找、分块查找全面详解

查找（Search）是数据结构中最基础、最常用的操作之一。本节重点讲解静态查找表中的三种经典算法：顺序查找、折半查找（二分查找）、分块查找。

一、基本概念回顾

静态查找表：只进行查找操作，不插入、不删除。
关键字（Key）：用于标识记录的某个数据项（如学号、ID）。
平均查找长度（ASL - Average Search Length）：衡量查找算法效率的核心指标。
ASL = Σ (每个元素被比较的概率 × 比较次数)

二、1. 顺序查找（Sequential Search）

定义

从表的一端开始，逐个将记录的关键字与给定值比较，直到找到或遍历完整个表。

适用场景

线性表（顺序存储或链式存储）
无序表或有序表均可（但有序时可优化提前终止）

算法实现（顺序表）

intSequentialSearch(intarr[],intn,intkey){for(inti=0;i<n;i++){if(arr[i]==key)returni;// 找到，返回下标}return-1;// 未找到}

优化：哨兵（Sentinel）顺序查找（减少一次判断）

intSequentialSearchWithSentinel(intarr[],intn,intkey){arr[0]=key;// 把0位置设为哨兵（需提前备份原arr[0]）inti=n-1;while(arr[i]!=key)i--;returni;// 如果i==0说明没找到，否则返回位置}

性能分析（最坏情况相同，平均不同）

情况	查找成功 ASL	查找失败 ASL	时间复杂度	空间复杂度
无序表	(n+1)/2	n	O(n)	O(1)
有序表（可提前终止）	≈ n/2（成功）	≈ n/2（失败）	O(n)	O(1)

优点：简单，实现容易，对数据无要求
缺点：效率低，适合小规模数据

三、2. 折半查找（Binary Search / 二分查找）

定义

前提：有序表（通常升序），每次将中间元素与关键字比较，将查找范围缩小一半。

算法实现（递归版 + 非递归版）

非递归版（推荐）

intBinarySearch(intarr[],intn,intkey){intlow=0,high=n-1;while(low<=high){intmid=low+(high-low)/2;// 避免溢出写法// int mid = (low + high) / 2; // 传统写法，可能溢出if(arr[mid]==key)returnmid;elseif(arr[mid]<key)low=mid+1;elsehigh=mid-1;}return-1;// 未找到}

递归版

intBinarySearchRecursive(intarr[],intlow,inthigh,intkey){if(low>high)return-1;intmid=low+(high-low)/2;if(arr[mid]==key)returnmid;elseif(arr[mid]<key)returnBinarySearchRecursive(arr,mid+1,high,key);elsereturnBinarySearchRecursive(arr,low,mid-1,key);}

性能分析

项目	值	说明
时间复杂度	O(log₂ n)	每次折半，查找次数最多 ⌊log₂ n⌋ + 1
查找成功 ASL	≈ log₂ (n+1) - 1
查找失败 ASL	≈ log₂ n
空间复杂度	O(1)（非递归） / O(log n)（递归）	递归调用栈深度
查找长度（决策树）	高度为 ⌊log₂ n⌋ + 1 的满二叉树

优点：效率极高，适合大规模有序数据
缺点：必须有序，且插入/删除代价大（需保持有序）

经典变种：

找第一个等于 key 的位置（处理重复元素）
找最后一个等于 key 的位置
找第一个大于等于 key 的位置（lower_bound）
找第一个大于 key 的位置（upper_bound）

四、3. 分块查找（Block Search / Indexed Sequential Search）

定义

折中方案：兼顾顺序查找的灵活性和折半查找的高效性。

核心思想：

将表分成若干块（块内无序或有序，块间有序）
建立一个索引表（每个块的最大关键字 + 块首地址）
先在索引表中折半查找确定目标块
再在块内顺序查找

数据结构

typedefstruct{intmaxKey;// 本块最大关键字intstart;// 本块在主表中的起始下标intlength;// 本块长度}IndexNode;IndexNode index[];// 索引表（已按 maxKey 升序排序）intdata[];// 主表（分块存储）

查找过程

在索引表中用折半查找，找到 maxKey ≥ key 的块
在该块内顺序查找 key

性能分析（假设分为 b 块，每块 s 个元素，n = b × s）

索引表折半查找：O(log₂ b)
块内顺序查找：平均 O(s/2)
总 ASL ≈ log₂ b + s/2

最优分块：当 log₂ b ≈ s/2 时效率最高，即块长 s ≈ √n，块数 b ≈ √n

项目	值
时间复杂度	O(√n + log₂ √n) ≈ O(√n)
空间复杂度	O(√n)（索引表）
ASL（最优）	≈ 2√n

优点：

比顺序查找快，比折半查找灵活（支持高效插入）
适合动态表（插入时只需在对应块尾插入，偶尔重建索引）

缺点：需要额外索引空间

五、三种查找算法对比总结表

查找方法	前提条件	时间复杂度（平均）	ASL（n=1000时近似）	空间复杂度	适用场景
顺序查找	无	O(n)	~500	O(1)	小数据量、无序表
折半查找	有序表	O(log₂ n)	~10	O(1)	大数据量、静态有序表
分块查找	块间有序	O(√n)	~63	O(√n)	动态表、需频繁插入、较大规模数据