考研数据结构之顺序查找、折半查找与分块查找详解（包含真题及解析）-EW帮帮网

考研数据结构之顺序查找、折半查找与分块查找详解

一、顺序查找（Sequential Search）

1.1 基本思想

顺序查找是最基础的查找算法，通过遍历数据集合逐个比较目标值与当前元素，直到找到匹配项或遍历结束。其核心特点是：

无序性：不要求数据有序，适用于任何存储结构
简单性：实现逻辑直观，但平均时间复杂度为O(n)

// 伪代码示例
int SequentialSearch(int arr[], int n, int key) {
    for(int i=0; i<n; i++) {
        if(arr[i] == key) return i;
    }
    return -1;
}

1.2 适用场景

小规模数据集合
动态变化频繁的线性表
无法预排序的场景

二、折半查找（Binary Search）

2.1 核心原理

折半查找通过分治策略将搜索区间逐步缩小，要求数据必须有序且顺序存储。典型步骤：

确定中间元素mid = (low + high)/2
比较目标值与中间元素
根据比较结果选择左/右子区间递归查找

// 递归实现示例
int BinarySearch(int arr[], int low, int high, int key) {
    if(low > high) return -1;
    int mid = (low + high) / 2;
    if(arr[mid] == key) return mid;
    else if(arr[mid] > key) 
        return BinarySearch(arr, low, mid-1, key);
    else 
        return BinarySearch(arr, mid+1, high, key);
}

2.2 性能分析

时间复杂度：O(log₂n)
空间复杂度：O(1)（非递归实现）
局限性：需静态有序表，插入删除成本高

三、分块查找（Block Search）

3.1 算法特性

分块查找结合了顺序查找和索引技术，通过分块索引表实现高效检索。其关键设计：

块内无序：每个数据块内部元素无需有序
块间有序：索引表中的块最大值保持升序排列
索引结构：包含块的最大关键字、起始位置等信息

3.2 实现步骤

构建索引表：将数据划分为若干子块，记录每块的最大值和起始地址
索引查找：在索引表中顺序/折半查找目标值所在块
块内查找：在确定的块内执行顺序查找

// 分块查找伪代码框架
typedef struct {
    int max_key;
    int start_pos;
} Index;

int BlockSearch(Index idx[], int block_num, int arr[], int key) {
    // 步骤1：索引表查找（可采用顺序或折半）
    int block_index = FindBlock(idx, block_num, key);
    if(block_index == -1) return -1;
    
    // 步骤2：块内顺序查找
    int start = idx[block_index].start_pos;
    while(arr[start] != key && start < ...) {
        start++;
    }
    return (arr[start] == key) ? start : -1;
}

3.3 性能平衡

平均查找长度：ASL = L_index + L_block
适用场景：大规模数据、动态变化频繁的场景

四、算法对比与考研重点

特性	顺序查找	折半查找	分块查找
时间复杂度	O(n)	O(logn)	O(√n)（典型情况）
空间要求	无需额外空间	需顺序存储	需索引表空间
数据要求	无序	严格有序	块间有序
动态性	支持动态插入	插入成本高	块内可动态扩展

考研高频考点：

折半查找判定树的构造与ASL计算
分块查找索引表的建立原则
各算法适用场景的综合分析

五、真题解析与考点突破

6.1 顺序查找真题

题目（2023年408真题）：

若线性表采用顺序存储结构，表中元素按查找概率降序排列，查找成功时的平均查找长度为多少？

解析：

关键点：顺序查找的ASL计算公式为ASL = (n+1)/2，但当元素按查找概率降序排列时，概率分布不均
解法：设概率序列为p1 ≥ p2 ≥ ... ≥ pn，则ASL = Σ(i=1→n) i*pi
答案：需根据具体概率分布计算，若概率均匀分布则退化为(n+1)/2

6.2 折半查找真题

题目（2022年数据结构考研真题）：

在12个互异元素构成的有序数组a[1…12]中进行折半查找，若待查找元素等于a[9]，则依次与哪些元素比较？

解析：

判定树构造：
- 初始区间[1,12]，mid=6 → 比较a[6]（排除左半区）
- 新区间[7,12]，mid=9 → 直接命中a[9]
比较序列：a[6] → a[9]
答案：依次比较a[6]和a[9]

6.3 分块查找真题

题目（严蔚敏题集改编）：

设计分块查找算法时，如何利用折半查找确定记录所在块？块内使用"监视哨"的优缺点是什么？

解析：

算法设计：
- 索引表按块最大值升序排列，使用折半查找确定目标值所在块
- 块内采用顺序查找（可加"监视哨"优化）
监视哨优缺点：
- 优点：减少边界条件判断，提升查找效率
- 缺点：需额外存储空间，可能破坏原数据结构
- 实现：将目标值暂存块尾作为哨兵，循环条件改为while(arr[i] != key)

6.4 综合应用题

题目（2024年模拟题）：

给定长度为n的有序表，设计算法在O(1)空间复杂度下实现折半查找，并说明如何避免整数溢出

解析：

非递归实现：

int BinarySearch(int arr[], int n, int key) {
    int low = 0, high = n-1;
    while(low <= high) {
        int mid = low + ((high - low) >> 1); // 防溢出写法
        if(arr[mid] == key) return mid;
        else if(arr[mid] < key) low = mid + 1;
        else high = mid - 1;
    }
    return -1;
}

防溢出技巧：使用mid = low + (high - low)/2代替(low+high)/2

六、备考建议

重点掌握：
- 折半查找判定树的构造与ASL计算（必考）
- 分块查找索引表与块内查找的时间复杂度关系
- 顺序查找的概率优化策略
实战技巧：
- 遇到"查找"类大题时，优先画出判定树/索引表结构
- 注意边界条件处理（如mid计算防溢出）
- 熟记ASL计算公式：
  顺序查找ASL = (n+1)/2
  折半查找ASL ≈ log2(n+1)-1

真题解析部分参考自等近年考题，建议结合《王道408真题解析》强化训练。

考研数据结构之顺序查找、折半查找与分块查找详解（包含真题及解析）