查找算法复习

查找算法的一些笔记。

顺序查找

最简单粗暴的查找方式,直接对数组进行遍历即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
* @author 陶波利
*/
public class OrderSearch {
public static boolean orderSearch(int[] arr, int key) {
for (int i = 0; i < arr.length; i++) {
if (arr[i] == key) {
return true;
}
}
return false;
}

public static void main(String[] args) {
int[] arr = {2, 3, 4, 5, 6, 7, 8, 12, 213, 45, 5123, 4123, 5};
int key = 5;
System.out.println(orderSearch(arr, key));
}
}

二分查找

二分查找要求数组有序,以下是在数组中使用二分查找算法查找 23 的例子(图源 GeeksforGeeks):

图源:GeeksforGeeks

代码:

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
/**
* @author 陶波利
*/
public class BinarySearch {
static int binarySearch(int[] arr, int x) {
int l = 0, r = arr.length - 1;
while (l <= r) {
int m = l + (r - l) / 2;
if (arr[m] == x) {
return m;
}
if (arr[m] < x) {
l = m + 1;
} else {
r = m - 1;
}
}
return -1;
}

public static void main(String[] args) {
int[] arr = {2, 3, 4, 5, 6, 7, 8, 12, 45, 213, 4123, 5123};
int x = 5123;
System.out.println(binarySearch(arr, x));
}
}

二分搜索树

关于二分搜索树查找算法在本人博客文章 BST 中的 contains() 方法中已经实现。GitHub:DataStructReview/BST.java at master · bolitao/DataStructReview

1
2
3
4
5
6
7
8
9
10
11
12
private boolean contains(Node root, E e) {
if (root == null) {
return false;
}
if (e.compareTo(root.e) == 0) {
return true;
} else if (e.compareTo(root.e) < 0) {
return contains(root.left, e);
} else {
return contains(root.right, e);
}
}

参考

Binary Search - GeeksforGeeks

Author: Boli Tao
Link: https://www.bolitao.xyz/archives/c4e8c16b.html
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.