小菜鸟

java菜鸟号正在起航

0%

查找算法

发表于 更新于 分类于 阅读次数： 32 Valine： 0
本文字数： 4.9k 阅读时长 ≈ 4 分钟

查找算法全解析：从线性到哈希的高效搜索策略

查找是数据处理中的核心操作，目的是从数据集合中找到满足特定条件的元素。根据数据结构和搜索策略的不同，查找算法的效率差异显著。本文详细解析线性查找、树查找、哈希查找等经典算法，涵盖原理、实现、复杂度及适用场景。

线性查找：遍历式搜索

线性查找是最基础的查找方式，通过逐个遍历数据元素实现搜索，无需数据有序。

1. 顺序查找（Sequential Search）

原理

遍历数据集合，将每个元素与目标值比较，找到则返回位置，否则返回不存在。

代码实现
1
2
3
4
5
6
7
8
public static int sequentialSearch(int[] arr, int target) {
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == target) {
            return i; // 找到目标，返回索引
        }
    }
    return -1; // 未找到
}
性能分析
  • 时间复杂度：
    • 最好：O (1)（目标在第一个位置）。
    • 最坏 / 平均：O (n)（需遍历全部元素）。
  • 空间复杂度：O (1)（仅需常量空间）。
适用场景
  • 无序数据集合（如未排序的数组、链表）。
  • 数据量小（大规模数据效率低）。

2. 二分查找（Binary Search）

原理

前提：数据必须有序（升序或降序）。
核心：每次通过与中间元素比较，将查找范围缩小一半（左半或右半），重复直至找到目标或范围为空。

代码实现（迭代版）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public static int binarySearch(int[] arr, int target) {
    int left = 0;
    int right = arr.length - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2; // 避免溢出（等价于 (left+right)/2）
        if (arr[mid] == target) {
            return mid; // 找到目标
        } else if (arr[mid] > target) {
            right = mid - 1; // 目标在左半部分
        } else {
            left = mid + 1; // 目标在右半部分
        }
    }
    return -1; // 未找到
}
性能分析
  • 时间复杂度：O (logn)（每次缩小一半范围，最多 log₂n 次比较）。
  • 空间复杂度：O (1)（迭代版）；递归版为 O (logn)（递归栈深度）。
优缺点
  • 优点：效率高，适合大规模有序数据。
  • 缺点：数据必须有序，插入 / 删除元素需维护有序性（时间复杂度 O (n)）。
适用场景
  • 静态有序数据（如字典、配置表），查询频繁但修改少。

3. 分块查找（Block Search）

原理

结合顺序查找和二分查找的优点，将数据分为若干块：

  • 块间有序：每块的最大元素小于下一块的最小元素。
  • 块内无序：块内元素可任意排列。
  • 索引表：存储每块的最大元素和起始索引（有序）。

步骤：

  1. 二分查找索引表，确定目标可能所在的块。
  2. 在对应块内顺序查找目标。
示例

数据：[16, 5, 9, 12, 21, 32, 24, 30, 35, 42, 51, 47]
分块：3 块 → [16,5,9,12]（最大 16）、[21,32,24,30]（最大 32）、[35,42,51,47]（最大 51）
索引表：[(16,0), (32,4), (51,8)]

查找目标 24：

  1. 二分索引表，确定 24 在第二块（32 ≥24 >16）。
  2. 在第二块[21,32,24,30]中顺序查找，找到索引 6。
性能分析
  • 时间复杂度：O (√n)（块数和块内元素数均为√n 时最优）。
  • 空间复杂度：O (n)（需存储索引表）。
适用场景
  • 数据量较大，且需兼顾查询与插入效率（块内无序，插入无需全表移动）。

查找树：基于树形结构的高效搜索

查找树通过树形结构组织数据，利用树的层级关系缩小查找范围，典型代表为二叉查找树和平衡二叉树。

1. 二叉查找树（Binary Search Tree, BST）

定义

满足以下条件的二叉树：

  • 左子树所有节点值 ≤ 根节点值。
  • 右子树所有节点值 ≥ 根节点值。
  • 左右子树均为二叉查找树。
查找原理

从根节点开始：

  • 目标值 = 根节点值 → 找到。
  • 目标值 < 根节点值 → 递归查找左子树。
  • 目标值 > 根节点值 → 递归查找右子树。
代码实现（查找与插入）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
public class BST<K extends Comparable<K>, V> {
    private Node root; // 根节点

    private class Node {
        K key;
        V value;
        Node left, right; // 左右子树
        int size; // 以该节点为根的树的节点数

        Node(K key, V value, int size) {
            this.key = key;
            this.value = value;
            this.size = size;
        }
    }

    // 查找键对应的值
    public V get(K key) {
        return get(root, key);
    }

    private V get(Node node, K key) {
        if (node == null) return null;
        int cmp = key.compareTo(node.key);
        if (cmp < 0) return get(node.left, key); // 左子树查找
        else if (cmp > 0) return get(node.right, key); // 右子树查找
        else return node.value; // 找到
    }

    // 插入键值对
    public void put(K key, V value) {
        root = put(root, key, value);
    }

    private Node put(Node node, K key, V value) {
        if (node == null) return new Node(key, value, 1); // 新节点
        int cmp = key.compareTo(node.key);
        if (cmp < 0) node.left = put(node.left, key, value); // 插入左子树
        else if (cmp > 0) node.right = put(node.right, key, value); // 插入右子树
        else node.value = value; // 更新值
        node.size = 1 + size(node.left) + size(node.right); // 更新节点数
        return node;
    }

    private int size(Node node) {
        return node == null ? 0 : node.size;
    }
}
性能分析
  • 时间复杂度：取决于树的高度。
    • 最好：O (logn)（平衡树，高度为 logn）。
    • 最坏：O (n)（退化为单链表，如插入有序数据）。
缺点
  • 性能不稳定，极端情况下效率低（如有序插入导致树倾斜）。

2. 平衡二叉树（AVL 树）

定义

二叉查找树的改进版，要求每个节点的左右子树高度差绝对值 ≤ 1（平衡因子：左子树高 - 右子树高，取值 {-1, 0, 1}）。

平衡维护：旋转操作

插入或删除节点可能导致失衡，需通过旋转调整结构恢复平衡。常见旋转方式：

失衡情况 旋转策略 示例场景
左子树过高（左 - 左） 右旋（顺时针） 根的左孩子的左子树插入节点
右子树过高（右 - 右） 左旋（逆时针） 根的右孩子的右子树插入节点
左子树的右子树过高（左 - 右） 先左旋左孩子，再右旋根 根的左孩子的右子树插入节点
右子树的左子树过高（右 - 左） 先右旋右孩子，再左旋根 根的右孩子的左子树插入节点
性能分析
  • 时间复杂度：O (logn)（树高严格控制在 logn 级别）。
  • 空间复杂度：O (n)（需存储每个节点的高度信息）。
适用场景
  • 需频繁插入、删除且要求稳定高效查询的场景（如数据库索引）。

哈希查找：基于哈希函数的常数级搜索

哈希查找通过哈希函数将目标值直接映射到存储位置，跳过遍历或树的层级查找，是平均效率最高的查找方式。

原理

  1. 哈希函数：将目标值（键）映射为数组索引（如 index = key % capacity）。
  2. 解决冲突：当不同键映射到同一索引时（哈希冲突），采用以下策略：
    • 拉链法：每个索引对应一个链表，冲突元素存入链表。
    • 线性探测法：冲突时依次检查下一个索引，直至找到空位。
拉链法实现（简化版）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
public class HashTable<K, V> {
    private Node[] table; // 哈希表数组
    private int size; // 元素个数
    private int capacity; // 数组容量

    private class Node {
        K key;
        V value;
        Node next; // 链表指针

        Node(K key, V value, Node next) {
            this.key = key;
            this.value = value;
            this.next = next;
        }
    }

    public HashTable(int capacity) {
        this.capacity = capacity;
        table = new Node[capacity];
    }

    // 哈希函数：计算索引
    private int hash(K key) {
        return (key.hashCode() & 0x7fffffff) % capacity; // 确保非负
    }

    // 查找
    public V get(K key) {
        int index = hash(key);
        Node node = table[index];
        while (node != null) {
            if (node.key.equals(key)) {
                return node.value; // 找到
            }
            node = node.next;
        }
        return null; // 未找到
    }

    // 插入
    public void put(K key, V value) {
        int index = hash(key);
        // 检查是否已存在，存在则更新
        for (Node node = table[index]; node != null; node = node.next) {
            if (node.key.equals(key)) {
                node.value = value;
                return;
            }
        }
        // 不存在则插入链表头部
        table[index] = new Node(key, value, table[index]);
        size++;
    }
}
性能分析
  • 平均时间复杂度：O (1)（哈希函数均匀且冲突少）。
  • 最坏时间复杂度：O (n)（所有元素冲突，链表退化为线性表）。
  • 空间复杂度：O (n)（存储哈希表和链表节点）。
适用场景
  • 数据量大、查询频繁且键分布均匀的场景（如缓存系统、字典）。

查找算法对比与选择

算法 时间复杂度（平均） 时间复杂度（最坏） 前提条件 适用场景
顺序查找 O(n) O(n) 无 小规模 / 无序数据
二分查找 O(logn) O(logn) 数据有序 静态有序数据，查询频繁
分块查找 O(√n) O(n) 块间有序 中大规模，需兼顾插入效率
二叉查找树 O(logn) O(n) 树形结构 动态数据，插入删除不频繁
AVL 树 O(logn) O(logn) 平衡二叉树 动态数据，需稳定高效
哈希查找 O(1) O(n) 键分布均匀 大规模数据，查询为主

选择建议

  • 优先考虑哈希查找（平均 O (1)），适用于键分布均匀的场景。
  • 有序数据且修改少 → 二分查找。
  • 动态数据且需稳定性能 → AVL 树。
  • 小规模或无序数据 → 顺序查找（实现简单）
相关文章

欢迎关注我的其它发布渠道

表情 | 预览
快来做第一个评论的人吧~
Powered By Valine
v1.3.10