03-查找算法

type
status
date
slug
summary
tags
category
icon
password

顺序查找

  • 适用： 无序数组/列表
  • 思路： 从头到尾依次比较
  • 时间复杂度： O(n)

二分查找

  • 要求： 数组必须有序
  • 思路： 每次将范围减半
  • 时间复杂度： O(log n)

哈希查找（Hash Table Lookup）

  • 使用结构： HashMap、HashSet
  • 时间复杂度： O(1)（理想状态），最坏 O(n)
  • 适合： 查找频繁、插入删除灵活

二叉搜索树查找

  • 结构： 每个节点左小右大
  • 平均时间复杂度： O(log n)；最坏 O(n)（退化为链表）
  • 红黑树 / AVL 树查找： 保证 O(log n) 最坏情况

红黑树查找

Java 中 TreeMap 和 TreeSet 就是基于红黑树：

插值查找

  • 适合：元素分布近似均匀的有序数组
  • 类似二分，但使用公式估算位置
  • 时间复杂度： O(log log n) 最好，O(n) 最坏

斐波那契查找

  • 类似二分，利用斐波那契数列控制分割点
  • 少用，教学研究为主

跳表（Skip List）

有序链表 + 多级索引，支持快速查找

B 树 / B+ 树

多路平衡查找树，常用于数据库/文件系统

Trie（字典树）

适用于前缀查找、词频统计、自动补全

Bloom Filter

高效判断“是否存在”，支持误判，不支持删除

并查集（Union-Find）

处理集合合并和查找问题，如图连通性等
 
算法
适用数据结构
平均时间
最坏时间
空间
顺序查找
无序数组
二分查找
有序数组
哈希查找
哈希表
BST 查找
二叉搜索树
AVL/红黑树查找
平衡二叉树
Trie 查找
字典树
跳表查找
跳表结构
 
上一篇
02-排序算法
下一篇
04-递归与分治
Loading...