1. 顺序查找#
顺序查找（Sequ序查找）是一种简单直接的查找算法，适用于在无序数组中查找特定元素。以下是Java实现的步骤解析和代码示例：
实现步骤#
- 方法定义：创建一个静态方法
sequentialSearch，接收整型数组和目标值作为参数。 - 遍历数组：使用
for循环逐个访问数组元素。 - 元素比较：检查当前元素是否等于目标值，若相等则立即返回当前索引。
- 处理未找到：遍历结束后仍未找到目标值，则返回-1。
Java代码实现#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| public class SequentialSearch {
public static int sequentialSearch(int[] arr, int target) {
for (int i = 0; i < arr.length; i++) {
if (arr[i] == target) {
return i; // 找到目标，返回索引
}
}
return -1; // 未找到，返回-1
}
public static void main(String[] args) {
int[] arr = {3, 5, 2, 7, 1};
System.out.println(sequentialSearch(arr, 5)); // 输出: 1
System.out.println(sequentialSearch(arr, 1)); // 输出: 4
System.out.println(sequentialSearch(arr, 9)); // 输出: -1
}
}
|
关键点说明#
- 时间复杂度：O(n)，最坏情况下需要检查所有元素。
- 适用场景：适用于小规模数据或未排序数组。
- 注意事项：若数组元素为对象类型，需使用
equals()方法进行比较，而非==运算符。
此实现简洁高效，能够正确处理空数组及不存在目标值的情况。
2. 二分查找#
二分查找（折半查找）是一种高效的查找算法，要求数据必须是有序的。其核心思想是通过不断缩小搜索范围来快速定位目标值。以下是 Java 实现及详细解析：
实现步骤#
- 数组有序：确保输入的数组是升序排列的（若降序需调整比较逻辑）
- 定义边界：初始化两个指针
low 和 high 分别指向数组的首尾 - 循环折半：
- 计算中间索引
mid = (low + high) / 2 - 比较中间元素与目标值：
- 若
arr[mid] == target，返回 mid（找到目标） - 若
arr[mid] < target，说明目标在右半部分，调整 low = mid + 1 - 若
arr[mid] > target，说明目标在左半部分，调整 high = mid - 1
- 终止条件：当
low > high 时，未找到目标，返回 -1
Java 代码实现#
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
| public class BinarySearch {
public static int binarySearch(int[] arr, int target) {
int low = 0;
int high = arr.length - 1;
while (low <= high) { // 注意循环条件
int mid = low + (high - low) / 2; // 避免整数溢出
if (arr[mid] == target) {
return mid; // 找到目标，返回索引
} else if (arr[mid] < target) {
low = mid + 1; // 搜索右半部分
} else {
high = mid - 1; // 搜索左半部分
}
}
return -1; // 未找到
}
public static void main(String[] args) {
int[] arr = {1, 3, 5, 7, 9, 11}; // 必须是有序数组
System.out.println(binarySearch(arr, 5)); // 输出: 2
System.out.println(binarySearch(arr, 11)); // 输出: 5
System.out.println(binarySearch(arr, 2)); // 输出: -1
}
}
|
关键点说明#
- 时间复杂度：O(log n)，效率远高于顺序查找
- 适用场景：有序数组（若无序需先排序，但排序成本需考虑）
- 避免整数溢出：
mid = low + (high - low) / 2 比 (low + high) / 2 更安全- 当
low + high 超过 Integer.MAX_VALUE 时，前者不会溢出
- 循环条件：必须是
low <= high，否则会漏查边界情况
扩展优化#
- 递归实现：可通过递归替代循环（但栈深度可能受限）
- 返回插入位置：若未找到目标，可返回应插入的位置（LeetCode 35题）
- 处理重复元素：修改代码返回第一个或最后一个匹配的索引
二分查找是经典的分治算法，理解其核心思想对学习其他高效算法（如快速排序、树结构）有重要帮助。
3. 哈希查找#
以下是Java实现哈希查找的步骤解析和代码示例：
哈希查找原理#
哈希查找基于哈希表实现，通过哈希函数将键映射到数组索引，实现快速访问。核心步骤包括：
- 哈希函数：将键转换为数组下标。
- 冲突处理：解决不同键映射到同一位置的问题（如链地址法）。
- 查找过程：定位索引后，在对应位置（链表/桶）中搜索目标。
实现步骤#
- 定义哈希表结构：使用数组+链表（链地址法）。
- 哈希函数设计：取键的哈希值并映射到数组范围。
- 插入数据：根据哈希值找到位置，处理冲突。
- 查找数据：定位索引后遍历链表，找到匹配键。
Java代码实现#
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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
| // 链表节点定义
class HashNode<K, V> {
K key;
V value;
HashNode<K, V> next;
public HashNode(K key, V value) {
this.key = key;
this.value = value;
this.next = null;
}
}
// 哈希表类
public class HashTable<K, V> {
private static final int DEFAULT_CAPACITY = 16;
private HashNode<K, V>[] buckets;
private int capacity;
// 初始化哈希表
public HashTable() {
this(DEFAULT_CAPACITY);
}
public HashTable(int capacity) {
this.capacity = capacity;
buckets = new HashNode[capacity];
}
// 哈希函数：键哈希值取模
private int getBucketIndex(K key) {
return (key.hashCode() & 0x7FFFFFFF) % capacity;
}
// 插入键值对
public void put(K key, V value) {
int index = getBucketIndex(key);
HashNode<K, V> node = buckets[index];
// 检查是否已存在相同键
while (node != null) {
if (node.key.equals(key)) {
node.value = value; // 更新值
return;
}
node = node.next;
}
// 插入新节点到链表头部
HashNode<K, V> newNode = new HashNode<>(key, value);
newNode.next = buckets[index];
buckets[index] = newNode;
}
// 哈希查找
public V get(K key) {
int index = getBucketIndex(key);
HashNode<K, V> node = buckets[index];
while (node != null) {
if (node.key.equals(key)) {
return node.value; // 找到目标值
}
node = node.next;
}
return null; // 未找到
}
// 测试代码
public static void main(String[] args) {
HashTable<String, Integer> table = new HashTable<>();
table.put("apple", 10);
table.put("banana", 20);
table.put("orange", 30);
System.out.println("apple: " + table.get("apple")); // 10
System.out.println("grape: " + table.get("grape")); // null
}
}
|
关键点说明#
哈希函数：
- 使用
key.hashCode() 获取哈希值。 & 0x7FFFFFFF 确保非负，% capacity 控制索引范围。
冲突处理：
- 链地址法：每个数组元素是链表头节点，冲突元素链接到同一桶中。
时间复杂度：
- 理想情况：O(1)（无冲突时直接访问）。
- 最坏情况：O(n)（所有键冲突，退化为链表遍历）。
动态扩容（扩展优化）：
- 当元素数量超过负载因子（如 0.75）时，扩容数组并重新哈希所有元素。
扩展优化方向#
- 动态调整容量：避免链表过长，提升查询效率。
- 红黑树优化：Java 8+的HashMap在冲突严重时，将链表转为红黑树，时间复杂度降为O(log n)。
- 开放寻址法：使用探测方法（线性探测、二次探测）替代链地址法。
通过上述实现，哈希查找能够高效处理数据查询，特别适合键值对存储场景。实际开发中，推荐直接使用Java内置的HashMap类，其经过高度优化且功能完善。
4. 二叉搜索树查找#
以下是Java实现二叉搜索树（BST）查找的详细步骤解析和代码示例：
二叉搜索树（BST）特性#
- 有序结构：每个节点的左子树所有节点值 小于 当前节点，右子树所有节点值 大于 当前节点。
- 查找原理：利用BST的有序性，通过比较目标值与当前节点值，逐步缩小搜索范围。
实现步骤#
- 定义节点类：包含节点值、左子节点和右子节点。
- 构建BST结构：定义二叉搜索树类，包含根节点。
- 实现查找方法：
- 递归法：从根节点开始，递归比较并进入左/右子树。
- 迭代法：通过循环替代递归，避免栈溢出风险。
- 测试验证：插入测试数据并验证查找结果。
Java代码实现#
1. 定义节点类#
1
2
3
4
5
6
7
8
9
10
11
| class TreeNode {
int val;
TreeNode left;
TreeNode right;
public TreeNode(int val) {
this.val = val;
this.left = null;
this.right = null;
}
}
|
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
56
57
58
59
60
61
62
63
64
65
66
67
68
| public class BinarySearchTree {
private TreeNode root;
// 递归查找
public boolean searchRecursive(int target) {
return searchRecursive(root, target);
}
private boolean searchRecursive(TreeNode node, int target) {
if (node == null) return false; // 基线条件：未找到
if (node.val == target) return true; // 找到目标值
if (target < node.val) {
return searchRecursive(node.left, target); // 递归左子树
} else {
return searchRecursive(node.right, target); // 递归右子树
}
}
// 迭代查找
public boolean searchIterative(int target) {
TreeNode current = root;
while (current != null) {
if (current.val == target) {
return true; // 找到目标值
} else if (target < current.val) {
current = current.left; // 进入左子树
} else {
current = current.right; // 进入右子树
}
}
return false; // 遍历结束未找到
}
// 插入节点（用于构建测试树）
public void insert(int val) {
root = insertNode(root, val);
}
private TreeNode insertNode(TreeNode node, int val) {
if (node == null) return new TreeNode(val); // 插入新节点
if (val < node.val) {
node.left = insertNode(node.left, val); // 递归左子树
} else if (val > node.val) {
node.right = insertNode(node.right, val); // 递归右子树
}
return node;
}
// 测试代码
public static void main(String[] args) {
BinarySearchTree bst = new BinarySearchTree();
// 构建测试树: 5
// / \
// 3 8
// / \ /
// 1 4 6
int[] values = {5, 3, 8, 1, 4, 6};
for (int val : values) {
bst.insert(val);
}
// 验证查找结果
System.out.println("递归查找 4: " + bst.searchRecursive(4)); // true
System.out.println("递归查找 7: " + bst.searchRecursive(7)); // false
System.out.println("迭代查找 6: " + bst.searchIterative(6)); // true
System.out.println("迭代查找 0: " + bst.searchIterative(0)); // false
}
}
|
关键点说明#
时间复杂度：
- 平均情况：O(log n)，树平衡时每次搜索范围减半。
- 最坏情况：O(n)，当树退化为链表时（如插入有序数据）。
空间复杂度：
- 递归法：O(h)，h为树高度，递归栈深度。
- 迭代法：O(1)，仅需常数空间。
平衡优化：
- 普通BST可能退化为链表，可通过 AVL树 或 红黑树 保持平衡，确保查找效率稳定在O(log n)。
应用场景：
- 动态数据集合的快速查找、插入、删除（如数据库索引）。
- 中序遍历可直接获得有序序列。
扩展对比#
| 查找方法 | 平均时间复杂度 | 最坏时间复杂度 | 数据要求 |
|---|
| 顺序查找 | O(n) | O(n) | 无序 |
| 二分查找 | O(log n) | O(log n) | 有序数组 |
| 哈希查找 | O(1) | O(n) | 无特殊要求 |
| 二叉搜索树查找 | O(log n) | O(n) | 需维护树结构有序 |
通过实现二叉搜索树的查找，可以深入理解树形结构在动态数据管理中的优势。实际开发中，优先使用Java内置的TreeMap或TreeSet（基于红黑树），它们已实现自动平衡优化。
5. 平衡二叉搜索树(如AVL树、红黑树)查找#
以下是Java实现平衡二叉搜索树（AVL树）查找的详细实现代码，包含旋转平衡机制和完整注释说明：
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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
| // AVL树节点定义
class AVLNode {
int key;
int height;
AVLNode left;
AVLNode right;
public AVLNode(int key) {
this.key = key;
this.height = 1; // 新节点初始高度为1
this.left = null;
this.right = null;
}
}
public class AVLTree {
private AVLNode root;
// 获取节点高度（处理空节点）
private int height(AVLNode node) {
return node == null ? 0 : node.height;
}
// 计算平衡因子（左子树高度 - 右子树高度）
private int balanceFactor(AVLNode node) {
return node == null ? 0 : height(node.left) - height(node.right);
}
// 更新节点高度（左右子树最大高度+1）
private void updateHeight(AVLNode node) {
if (node != null) {
node.height = Math.max(height(node.left), height(node.right)) + 1;
}
}
// 右旋操作（处理LL型不平衡）
private AVLNode rightRotate(AVLNode y) {
AVLNode x = y.left;
AVLNode T3 = x.right;
x.right = y;
y.left = T3;
updateHeight(y);
updateHeight(x);
return x;
}
// 左旋操作（处理RR型不平衡）
private AVLNode leftRotate(AVLNode x) {
AVLNode y = x.right;
AVLNode T2 = y.left;
y.left = x;
x.right = T2;
updateHeight(x);
updateHeight(y);
return y;
}
// 平衡节点（根据平衡因子执行旋转）
private AVLNode rebalance(AVLNode node) {
int bf = balanceFactor(node);
// 左子树高（LL或LR型）
if (bf > 1) {
if (balanceFactor(node.left) < 0) { // LR型
node.left = leftRotate(node.left);
}
return rightRotate(node);
}
// 右子树高（RR或RL型）
if (bf < -1) {
if (balanceFactor(node.right) > 0) { // RL型
node.right = rightRotate(node.right);
}
return leftRotate(node);
}
return node; // 已平衡无需调整
}
// 插入节点（递归实现）
public void insert(int key) {
root = insert(root, key);
}
private AVLNode insert(AVLNode node, int key) {
if (node == null) return new AVLNode(key);
if (key < node.key) {
node.left = insert(node.left, key);
} else if (key > node.key) {
node.right = insert(node.right, key);
} else {
return node; // 不允许重复键
}
updateHeight(node);
return rebalance(node);
}
// 查找方法（迭代实现）
public boolean search(int key) {
AVLNode current = root;
while (current != null) {
if (key == current.key) {
return true;
} else if (key < current.key) {
current = current.left;
} else {
current = current.right;
}
}
return false;
}
// 中序遍历验证树结构
public void inOrder() {
inOrder(root);
System.out.println();
}
private void inOrder(AVLNode node) {
if (node != null) {
inOrder(node.left);
System.out.print(node.key + " ");
inOrder(node.right);
}
}
// 测试代码
public static void main(String[] args) {
AVLTree tree = new AVLTree();
// 测试插入后自动平衡
int[] keys = {10, 20, 30, 40, 50, 25};
for (int key : keys) {
tree.insert(key);
}
System.out.print("中序遍历结果: ");
tree.inOrder(); // 输出: 10 20 25 30 40 50
// 验证查找功能
System.out.println("查找25: " + tree.search(25)); // true
System.out.println("查找35: " + tree.search(35)); // false
// 验证平衡性（查看根节点应为30）
System.out.println("根节点: " + tree.root.key); // 30
}
}
|
关键实现原理说明：#
平衡维护机制：
- 节点高度：每个节点存储当前子树高度
- 平衡因子：通过左右子树高度差判断平衡状态（绝对值>1时触发旋转）
- 四种旋转操作：
- 左旋（RR型不平衡）
- 右旋（LL型不平衡）
- 先左后右旋（LR型不平衡）
- 先右后左旋（RL型不平衡）
时间复杂度：
- 查找：O(log n)（始终维持树平衡）
- 插入：O(log n)（需要回溯调整平衡）
与普通BST对比优势：
- 消除极端情况退化（保证最坏情况性能）
- 查询效率稳定（适合高频查询场景）
- 自动动态平衡（无需人工干预）
执行流程示例（插入30后的平衡调整）：#
1
2
3
4
5
6
7
8
9
| 原始插入顺序：10 → 20 → 30
1. 插入10（平衡）
2. 插入20（平衡）
3. 插入30触发RR型不平衡
4. 执行左旋操作后恢复平衡
最终树结构：
20
/ \
10 30
|
扩展优化方向：#
- 删除操作实现：需要类似插入的平衡调整
- 支持泛型：实现Comparable接口支持多种数据类型
- 性能监控：添加统计旋转次数的功能
- 可视化输出：生成树形结构图帮助调试
该实现完整展示了AVL树的核心平衡机制，相比普通二叉搜索树，通过增加约30%的代码量换来了查询性能的稳定性保障，适合需要严格保证查询效率的场景。