参考书目：《大话数据结构》
文章目录
- 一、哨兵法
- 二、折半 / 二分 查找
- 三、插值查找
- 四、斐波那契查找
一、哨兵法
1.思路图解：
2.代码实现：
public class SentrySearch {
public static int search(int[] a, int key) {
int i;
a[0] = key; // 设置a[0]存储要查找的值，称之为“哨兵”
i = a.length - 1; // 循环从数组尾部开始
while (a[i] != key) {
i--;
}
return i;
}
}3.分析：
- 时间复杂度：O(n)
- 优：算法简单，对于静态查找表的记录没有任何要求，也适用于一些小型数据的查找
- 劣：当n很大时，查找效率低下
- 改：可以将易查到的记录放在查找的开始端附近，而不常用的记录放在查找的结束端附近。
- 注：哨兵既可以在数组头，也可以在数组尾，哨兵法是一种顺序查找表的优化
二、折半 / 二分 查找
1.思路图解：
2.代码实现：
public class BinarySearch {
public static int search(int[] a, int key) {
int low = 1;
int high = a.length - 1;
int mid;
while (low <= high) {
mid = low + (high - low) / 2; // 防止溢出
if (key < a[mid]) {
high = mid - 1;
} else if (key > a[mid]) {
low = mid + 1;
} else {
return mid;
}
}
return 0;
}
}3.分析：
- 时间复杂度：O(logn)
- 优：对于静态查找表，一次排序后不再变化，效率较高，适合使用
- 劣：查找的前提条件是有序顺序存储，对于需要频繁执行插入和删除操作的数据集来说，维护有序的排序有不小的工作量，就不建议使用
三、插值查找
1.思路图解：
2.代码实现：
public class InterSearch {
public static int search(int[] a, int key) {
int low = 1;
int high = a.length - 1;
int mid;
try {
while (low <= high) {
mid = low + ((key - a[low]) / (a[high] - a[low])) * (high - low); // 自适应的mid
if (key < a[mid]) {
high = mid - 1;
} else if (key > a[mid]) {
low = mid + 1;
} else {
return mid;
}
}
} catch (Exception e) {
System.out.println("计算自适应的mid时，mid值未计算成功~");
}
return 0;
}
}3.分析：
- 时间复杂度：O(logn)
- 优：对于表长较大，而关键字分布较均匀的查找表来说，其插值查找的平均性能比折半查找好得多
- 劣：关键字分布很不均匀，则不建议使用
四、斐波那契查找
1.思路图解：
2.代码实现
public class FibonacciSearch {
public static int[] fib() {
int[] F = new int[101];
F[0] = 1;
F[1] = 1;
for (int i = 2; i < 101; i++) {
F[i] = F[i - 1] + F[i - 2];
}
return F;
}
public static int search(int[] a, int key) {
int[] F = fib();
int n = a.length - 1;
int low = 0;
int high = n;
int mid = 0;
int k = 0;
while (high > F[k] - 1) k++;
a = Arrays.copyOf(a, F[k]);
for (int i = n + 1; i < F[k] - 1; i++) {
a[i] = F[n];
}
while (low <= high && k >= 1) {
mid = low + F[k - 1] - 1;
if (a[mid] < key) {
low = mid + 1;
k -= 2;
} else if (a[mid] > key) {
high = mid - 1;
k--;
} else {
if (mid <= n) {
return mid;
} else {
return a[n];
}
}
}
if (k < 1 && a[n] == key) return n;
return -1;
}
}3.分析：
- 时间复杂度：O(logn)
- 优：如果要查找的记录在右侧，则左侧的数据都不用判断，不断反复进行下去，效率较高，且平均性能优于折半查找
- 劣：相反的情况下效率较低
总分析：折半查找是进行加法与除法运算，插值查找是进行复杂的四则运算，而斐波那契查找是进行简单的加减法运算，在海量的数据的查找过程中，这些细微的差别可能会影响最终的查找效率。这三种有序表的查找（注：1为顺序表的查找，2、3、4为有序表的查找）本质上是分割点的选择不同，各有优劣，实际开发中应综合考虑数据的特点，再做出选择。