查找算法

一、考纲要求

掌握各种查找算法的基本思想和实现方法
理解不同查找算法的时间复杂度和空间复杂度
能够根据实际场景选择合适的查找算法
掌握哈希表的构建和冲突处理方法
了解二叉排序树的性质及其查找过程

二、查找算法概述

查找是根据给定的关键字K，在查找表中确定一个其关键字等于K的数据元素（或记录）。查找算法主要分为两类：

静态查找：查找表结构固定不变，只进行查找操作
动态查找：在查找过程中可以插入和删除记录

常见的查找算法包括：

顺序查找（线性查找）
二分查找（折半查找）
分块查找（索引查找）
哈希查找（散列查找）
二叉排序树查找

三、顺序查找

3.1 基本思想

从表的一端开始，顺序扫描查找表，将给定值k与表中每个元素的关键字进行比较，若找到关键字等于k的元素，则查找成功；否则，扫描完整个表仍未找到关键字等于k的元素，则查找失败。

3.2 算法实现

int SequentialSearch(int S[], int n, int key) {
    for (int i = 0; i < n; i++) {
        if (S[i] == key) {
            return i;  // 查找成功，返回下标
        }
    }
    return -1;  // 查找失败
}

3.3 性能分析

时间复杂度：O(n)
空间复杂度：O(1)
最好情况：O(1)（第一个元素就是要查找的元素）
最坏情况：O(n)（要查找的元素不在表中或在表的最后一个位置）
平均情况：O(n)

3.4 适用场景

查找表无序时
元素个数较少时
作为其他查找算法的补充

四、二分查找

4.1 基本思想

对有序表进行二分查找，开始时将区间定位在整个表中。若待查关键字与中间位置元素的关键字相等，则查找成功；若待查关键字小于中间位置元素的关键字，则在前半区继续查找；否则在后半区继续查找。每次比较使查找范围缩小一半。

4.2 算法实现

int BinarySearch(int S[], int n, int key) {
    int low = 0, high = n - 1;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (S[mid] == key) {
            return mid;  // 查找成功
        } else if (S[mid] < key) {
            low = mid + 1;  // 在后半区查找
        } else {
            high = mid - 1;  // 在前半区查找
        }
    }
    return -1;  // 查找失败
}

4.3 性能分析

时间复杂度：O(log₂n)
空间复杂度：O(1)
最好情况：O(1)（中间元素就是要查找的元素）
最坏情况：O(log₂n)（要查找的元素在表的一端或不在表中）
平均情况：O(log₂n)

4.4 适用场景

查找表有序时
元素个数较多时
需要高效查找时

4.5 注意事项

必须建立在有序表之上
对于频繁插入删除的表，维护有序性的开销较大
可以递归实现，但迭代实现更节省空间

五、分块查找

5.1 基本思想

分块查找是顺序查找和二分查找的折中方案。将查找表分为若干块，每块内部无序但块之间有序（即前一块的最大元素小于后一块的最小元素）。查找过程分两步：

先对块进行查找（可以用顺序查找或二分查找），确定关键字所在的块
在确定的块内部进行顺序查找

5.2 表结构

设查找表有n个元素，分为b块，则每块的元素个数为s = n/b（假设均匀分布）。每块需要一个索引项，包含该块的最大关键字和该块在表中的起始位置。

5.3 算法实现

typedef struct {
    int maxKey;      // 块内最大关键字
    int startIndex;  // 块在表中的起始位置
} IndexItem;

int BlockSearch(int S[], int n, int key, IndexItem index[], int b) {
    // 第一步：在索引表中查找关键字所在的块
    int low = 0, high = b - 1;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (index[mid].maxKey == key) {
            // 在索引表中找到精确匹配
            return index[mid].startIndex;  // 返回块的起始位置
        } else if (index[mid].maxKey < key) {
            low = mid + 1;  // 在后半区查找
        } else {
            high = mid - 1;  // 在前半区查找
        }
    }
    // 循环结束后，low是第一个maxKey大于key的块的索引
    // 因此关键字应该在low-1块中（如果low>0的话）
    int blockIndex = (low > 0) ? low - 1 : 0;
    if (blockIndex >= b) blockIndex = b - 1;
    
    // 第二步：在确定的块内进行顺序查找
    int start = index[blockIndex].startIndex;
    int end = (blockIndex == b - 1) ? n - 1 : index[blockIndex + 1].startIndex - 1;
    
    for (int i = start; i <= end; i++) {
        if (S[i] == key) {
            return i;  // 查找成功
        }
    }
    return -1;  // 查找失败
}

5.4 性能分析

设表长为n，块数为b，则每块长度为s=n/b

第一步：在索引表（长度为b）上查找：O(log₂b) 或 O(b)（取决于使用二分还是顺序）
第二步：在块内部顺序查找：O(s) = O(n/b)
总时间复杂度：O(log₂b + n/b) 或 O(b + n/b)
当b ≈ √n时，时间复杂度达到最小：O(√n)
空间复杂度：O(b)（存储索引表）

5.5 适用场景

元素个数中等时（几千到几万）
插入删除操作不频繁时
作为顺序查找和二分查找之间的折中方案

六、哈希查找

6.1 基本思想

哈希查找（散列查找）是根据关键字直接计算出该元素在表中的存储位置，从而实现快速查找。其核心思想是通过哈希函数H(key)将关键字映射到哈希表的一个地址上。

6.2 哈希函数的构造方法

直接定址法：H(key) = a·key + b（a、b为常数）
数字分析法：取关键字的某几位作为哈希地址
平方取中法：取关键字平方后的中间几位作为哈希地址
折叠法：将关键字分割成几部分，然后相加取后几位作为哈希地址
除留余数法：H(key) = key mod p（p为不大于哈希表长度的素数）
随机数法：H(key) = random(key)（random为随机函数）

6.3 处理冲突的方法

当两个不同的关键字通过哈希函数映射到同一地址时，称为发生冲突（Collision）。

6.3.1 开放定址法（Open Addressing）

当发生冲突时，以探测序列的形式在哈希表中寻找下一个空闲地址。

线性探测：H_i = (H(key) + i) mod m
二次探测：H_i = (H(key) + i²) mod m
伪随机探测：H_i = (H(key) + d_i) mod m（d_i为伪随机数序列）

6.3.2 链地址法（Chaining）

将哈希值相同的元素链接在同一个单链表中。哈希表的每个单元存放一个指针，指向链表的头结点。

6.3.3 再哈希法

同时构造多个不同的哈希函数：H_i = RH_i(key)（i=1,2,...,k），当发生冲突时，再计算另一个哈希函数地址，直到不发生冲突为止。

6.3.4 建立公共溢出区

将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表。

6.4 算法实现（以链地址法为例）

#define TABLE_SIZE 100

typedef struct Node {
    int key;
    int value;
    struct Node* next;
} Node;

Node* hashTable[TABLE_SIZE];  // 哈希表

// 哈希函数（除留余数法）
int hash(int key) {
    return key % TABLE_SIZE;
}

// 插入元素
void insert(int key, int value) {
    int index = hash(key);
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->key = key;
    newNode->value = value;
    newNode->next = hashTable[index];
    hashTable[index] = newNode;
}

// 查找元素
int search(int key) {
    int index = hash(key);
    Node* current = hashTable[index];
    while (current != NULL) {
        if (current->key == key) {
            return current->value;  // 查找成功
        }
        current = current->next;
    }
    return -1;  // 查找失败
}

6.5 性能分析

时间复杂度：O(1)（平均情况），最坏情况为O(n)（所有元素都映射到同一位置）
空间复杂度：O(n + m)（n为元素个数，m为哈希表长度）
装填因子α = n/m（n为元素个数，m为哈希表长度）：
- 开放定址法：查找成功平均长度为(1 + 1/(1-α))/2，查找失败平均长度为(1 + 1/(1-α)²)/2
- 链地址法：查找成功平均长度为1 + α/2，查找失败平均长度为α

6.6 适用场景

查找、插入、删除操作都非常频繁时
对查找速度要求很高时
元素分布较均匀时
内存允许开辟较大空间时

七、二叉排序树查找

7.1 基本思想

二叉排序树（Binary Search Tree, BST）是一棵空树或具有以下性质的二叉树：

若左子树不空，则左子树上所有结点的值均小于它的根结点的值
若右子树不空，则右子树上所有结点的值均大于它的根结点的值
左、右子树也分别为二叉排序树
没有键值相等的节点（即没有相同的关键字）

查找过程：从根节点开始，比较根节点关键字与给定值：

若相等，则查找成功
若给定值小于根节点关键字，则在左子树中继续查找
若给定值大于根节点关键字，则在右子树中继续查找
若到达空子树仍未找到，则查找失败

7.2 算法实现

typedef struct BSTNode {
    int key;
    int value;
    struct BSTNode* left;
    struct BSTNode* right;
} BSTNode;

// 查找元素
BSTNode* BSTSearch(BSTNode* root, int key) {
    if (root == NULL || root->key == key) {
        return root;  // 查找成功（找到节点）或查找失败（空树）
    }
    if (key < root->key) {
        return BSTSearch(root->left, key);  // 在左子树中查找
    } else {
        return BSTSearch(root->right, key);  // 在右子树中查找
    }
}

// 非递归实现
BSTNode* BSTSearch_NoRec(BSTNode* root, int key) {
    while (root != NULL && root->key != key) {
        if (key < root->key) {
            root = root->left;
        } else {
            root = root->right;
        }
    }
    return root;  // 返回找到的节点或NULL
}

7.3 性能分析

时间复杂度：
- 最好情况：O(log₂n)（树平衡时）
- 最坏情况：O(n)（树退化为链表时，如有序序列构建BST）
- 平均情况：O(log₂n)（假设所有可能的二叉排序树出现的概率相等）
空间复杂度：O(h)（h为树的高度，递归时为栈空间）

7.4 构建二叉排序树

BSTNode* insertBST(BSTNode* root, int key, int value) {
    if (root == NULL) {
        // 创建新节点
        BSTNode* newNode = (BSTNode*)malloc(sizeof(BSTNode));
        newNode->key = key;
        newNode->value = value;
        newNode->left = newNode->right = NULL;
        return newNode;
    }
    if (key < root->key) {
        root->left = insertBST(root->left, key, value);
    } else if (key > root->key) {
        root->right = insertBST(root->right, key, value);
    }
    // 如果key已存在，则不插入（或者可以选择更新值）
    return root;
}

7.5 适用场景

需要频繁插入、删除和查找操作时
数据呈随机分布时（能够保持较好的平衡性）
作为动态查找表的实现方式
但需要注意：若输入数据是有序的，则会导致树严重失衡，此时应考虑使用平衡二叉树（如AVL树、红黑树）

八、各查找算法性能比较

查找算法	时间复杂度（平均）	时间复杂度（最坏）	空间复杂度	前置条件	适用场景
顺序查找	O(n)	O(n)	O(1)	无	小规模、无序表
二分查找	O(log₂n)	O(log₂n)	O(1)	有序表	大规模有序静态表
分块查找	O(√n)	O(√n)	O(√n)	块内无序、块间有序	中等规模、查找为主
哈希查找	O(1)	O(n)	O(n+m)	无	查找为主、要求O(1)查找
二叉排序树查找	O(log₂n)	O(n)	O(n)	无	动态查找表、插入删除频繁

九、高频考点分析

9.1 必考题型

算法时间复杂度分析：经常考察各查找算法在不同情况下的时间复杂度
算法实现：要求用C语言实现某个查找算法
算法对比：比较不同查找算法的优缺点和适用场景
哈希函数构造：考察常用哈希函数的设计方法
冲突处理方法：考察开放定址法、链地址法等冲突处理技术
二叉排序树性质：考察BST的查找、插入、删除过程及其时间复杂度

9.2 常见失分点

忘记二分查找必须在有序表上进行
混淆顺序查找和二分查找的时间复杂度
哈希函数设计不当导致冲突过多
开放定址法中的聚集问题（ primary clustering 和 secondary clustering ）
链地址法中链表过长导致性能下降
二叉排序树在极端情况下退化为链表的情况
分块查找中块大小的确定方法

9.3 解题技巧

先明确查找表的性质（有序/无序、静态/动态）
根据数据规模选择合适的算法
注意算法的边界条件（空表、单元素表等）
哈希查找要考虑装填因子和冲突处理方法
二叉排序树要注意平衡性问题
分块查找要记住“块内无序、块间有序”的特点
时间复杂度分析要考虑最好、最坏和平均情况

十、典型例题

例题1：二分查找变种

已知一个有序数组 A[0..n-1]，求第一个大于等于给定值 key 的元素位置。

解题思路：这是二分查找的变种，修改判断条件即可。

int lowerBound(int A[], int n, int key) {
    int low = 0, high = n - 1;
    int result = n;  // 默认返回n（表示所有元素都小于key）
    
    while (low <= high) {
        int mid = (low + high) / 2;
        if (A[mid] >= key) {
            result = mid;  // 可能的答案，继续向左找更小的索引
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    return result;
}

例题2：哈希冲突计算

哈希表长度为11，使用除留余数法 H(key) = key mod 11，已插入关键字：{15, 26, 27, 30, 28, 39}，问发生冲突的次数。

解题步骤：

计算每个关键字的哈希地址：
- 15 mod 11 = 4
- 26 mod 11 = 4（与15冲突，第1次冲突）
- 27 mod 11 = 5
- 30 mod 11 = 8
- 28 mod 11 = 6
- 39 mod 11 = 6（与28冲突，第2次冲突）
总冲突次数：2次

例题3：二叉排序树查找路径

已知关键字序列 {45, 24, 53, 12, 37, 48, 75} 按此顺序插入到空的二叉排序树中，查找关键字 37 的查找路径。

解题步骤：

构建二叉排序树：
- 插入45：根节点
- 插入24：45的左子节点
- 插入53：45的右子节点
- 插入12：24的左子节点
- 插入37：24的右子节点（因为12<37<24？不对，应该是：24<37<45，所以是24的右子节点）
- 插入48：53的左子节点
- 插入75：53的右子节点
查找路径：45 → 24 → 37
路径长度：3（经过3个节点）

十一、总结与建议

11.1 算法选择原则

小规模无序表（n<50）：顺序查找简单直接
大规模有序静态表：二分查找效率最高
中等规模查找为主表：分块查找折中选择
查找、插入、删除都频繁的动态表：
- 如果要求O(1)查找：哈希表
- 如果需要有序遍历：平衡二叉树（AVL/红黑树）
内存受限且查找不频繁：顺序查找或分块查找

11.2 学习建议

重点掌握：二分查找、哈希查找（尤其是哈希函数设计和冲突处理）、二叉排序树的基本操作
重点理解：各算法的时间空间复杂度分析方法
重点練習：用代码实现各种查找算法，尤其是带有边界条件的变种问题
重点對比：熟悉各算法的优缺点和适用场景，能够根据具体问题选择合适的算法
重點擴展：了解平衡二叉树（AVL树、红黑树）、B树、B+树等高级查找结构

11.3 考试提醒

查找算法在软考软件设计师中考查比例适中，通常会有1-2道选择题和1道综合题
选择题考点：时间复杂度、空间复杂度、适用场景、算法特点
综合题考点：算法实现、性能分析、哈希函数设计、冲突处理、二叉排序树操作
注意题目可能会给出具体数据要求计算查找次数或比较算法性能
哈希查找和二叉排序树是考查重点，要掌握细节

注：本博客内容参考《软件设计师教程（第5版）》及相关考试大纲编写，适用于软考软件设计师查找算法章节的学习和复习。生成时间：2026-03-14 16:30

查找算法 ​

一、考纲要求 ​

二、查找算法概述 ​

三、顺序查找 ​

3.1 基本思想 ​

3.2 算法实现 ​

3.3 性能分析 ​

3.4 适用场景 ​

四、二分查找 ​

4.1 基本思想 ​

4.2 算法实现 ​

4.3 性能分析 ​

4.4 适用场景 ​

4.5 注意事项 ​

五、分块查找 ​

5.1 基本思想 ​

5.2 表结构 ​

5.3 算法实现 ​

5.4 性能分析 ​

5.5 适用场景 ​

六、哈希查找 ​

6.1 基本思想 ​

6.2 哈希函数的构造方法 ​

6.3 处理冲突的方法 ​

6.3.1 开放定址法（Open Addressing） ​

6.3.2 链地址法（Chaining） ​

6.3.3 再哈希法 ​

6.3.4 建立公共溢出区 ​

6.4 算法实现（以链地址法为例） ​

6.5 性能分析 ​

6.6 适用场景 ​

七、二叉排序树查找 ​

7.1 基本思想 ​

7.2 算法实现 ​

7.3 性能分析 ​

7.4 构建二叉排序树 ​

7.5 适用场景 ​

八、各查找算法性能比较 ​

九、高频考点分析 ​

9.1 必考题型 ​

9.2 常见失分点 ​

9.3 解题技巧 ​

十、典型例题 ​

例题1：二分查找变种 ​

例题2：哈希冲突计算 ​

例题3：二叉排序树查找路径 ​

十一、总结与建议 ​

11.1 算法选择原则 ​

11.2 学习建议 ​

11.3 考试提醒 ​