查找算法的一些笔记。
顺序查找
最简单粗暴的查找方式，直接对数组进行遍历即可。
/**
* @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）：
代码：
/**
* @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
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);
}
}