企业官网建设流程全解析

【数据结构-查找篇】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说明没找到，否则返回位置}

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

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

三、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);}

性能分析

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

经典变种：

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

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

定义

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

核心思想：

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

数据结构

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

查找过程

1. 在索引表中用折半查找，找到 maxKey ≥ key 的块
2. 在该块内顺序查找 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

优点：

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

缺点：需要额外索引空间

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

六、实际应用场景举例

• 顺序查找：小配置文件读取、链表查找
• 折半查找：字典序查询、标准库 lower_bound/upper_bound、Java Arrays.binarySearch
• 分块查找：数据库索引早期实现、文件系统块索引、适合“读多写少但有插入”的场景

七、总结一句话

• 顺序查找：简单粗暴，适合小数据
• 折半查找：高效极致，但要求严格有序且静态
• 分块查找：折中方案，平衡了效率与灵活性，是动态查找的良好过渡

掌握这三种算法，不仅能应对考试和面试（尤其是 ASL 计算和适用场景判断），也为后续学习散列表、二叉排序树、B树/B+树打下坚实基础。

有想看具体 ASL 计算过程、变种二分实现代码、或者动态演示的，随时告诉我，我继续拆给你看～