- 第八章 有序数组查找
- 8.1 二分查找
- 8.2 插值查找
- 8.3 斐波那契查找
- 8.3.1 斐波那契数列
- 8.3.2 斐波那契查找
- 8.x 总结回顾
- 8.y 脑海练习
- 参考答案
- 第八章答案
内容导视：
- 二分查找
- 插值查找
- 斐波那契查找
前提：数组中的元素必须是顺序排列
Binary Search
玩过猜数游戏吗？如给定一个数，让你在 [1，100] 去猜，猜错了，会提示你猜的数是小了还是大了，最多只能猜 8 次。
如果使用前面的顺序查找，是不是有可能猜 100 次？
比较有效率的一种做法就是对半猜，每次都取范围内的中间数：猜 50，大了，范围被限定在 [1，50）；向左猜 25，小了，答案在 (25，50）区间；向右猜 37，小了，此时的答案就被限制在 (37，50）中…
那么查找元素时也可以使用这种方法，但是要求数组中元素必须是顺序。
思想：取中间元素与给定值比较，若相等，查找成功；若给定值大于中间元素，则在中间元素的右半部分查找，否则在左半部分查找。
找数 num，取中间数 arr[mid]，若 num > arr[mid]，就在右边 [mid+1, n - 1] 范围内找；若 num < arr[mid]，在左边 [0, mid - 1] 找；重复以上过程，直到 num = arr[mid] 或查找范围内无元素为止；记查找范围为 [start, end]。
public static int binarySearch(int[] arr, int num) {
int start = 0;
int end = arr.length - 1;
// 若 start > end，则范围内无元素，查找失败，返回 -1
while (start <= end) {
// 取范围内的中间值
int mid = start + (end - start) / 2;
int midVal = arr[mid];
if (num < midVal) {
end = mid - 1;
} else if (num > midVal) {
start = mid + 1;
} else {
return mid;
}
}
// 到这里说明没有找到 num，返回 -1
return -1;
}
二分查找每次都将查找范围缩小一半，到一个元素为止，平均时间复杂度为 O(logkn）。
8.2 插值查找Interpolation Search
当元素分布均匀时，可以通过控制权重的方法，使得 mid 更加接近要查找的元素 num 所在位置。
举例：{2、5、… 、1000000} 近百万长度的数组中，寻找元素 8 的下标，如果使用二分查找，不偏不倚从 50 万、25 万、12.5 万… 开始慢慢向左找，权重为 1/2，还是慢了。
我们可以观察到，8 相比 100 万而言十分地小，应该从更靠左的地方开始找，而不是从中间。
只需改动一点代码：
int weight = (num - arr[start]) / (arr[end] - arr[start]); int mid = start + (end - start) * weight;
当要查找的数 num 特别靠近范围的左端 arr[start] 时，分子值、权重（weight）趋向于 0，那么 mid 趋向 start，舍弃了右大半部分的查找范围；
当 num 处于中间时，weight 趋向 1/2，mid 也会在中间附近开始查找。
当 num 特别靠近 arr[end] 时，weight 趋向 1，mid 会更加接近 end。
可以验证，比如 {0，1，2，3，4，…，10000000} 中寻找 1 的下标：
初始值：start = 0，end = 10000000; weight = (1 - 0) / (10000000 - 0) = 0; mid = 0 + (10000000 - 0) * 0 = 0; 1 > arr[0]，向右找，start = 0 + 1 = 1; 下一次循环，weight = (1 - 1) / (1000000 - 1) = 0; mid = 1 + (1000000 - 1) * 0 = 1; 1 = arr[1]，找到了，只需两次。
要是使用二分法，需要 ⌊log210000000⌋ - 1 = 22 次。
但是需要注意由于这种方式依赖 num 得出下标，所以 num 的值要在 arr[start]、arr[end] 之间，否则会计算出负数，导致下标越界。
可以在循环之前加入：
if (num < arr[start] || num > arr[end]) {
return -1;
}
8.3 斐波那契查找
除了对半分，还有黄金分割；不知道你们听说过斐波那契数列没有，随着 n 的增大，相邻两个斐波那契数的比值 f(n）/ f(n+1）会逐渐趋向黄金分割比 0.61803398…，下面我们就利用斐波那契数列完成分割。
8.3.1 斐波那契数列Fibonacci sequence：{1，1，2，3，5，8，13，21，34 …}
性质：数组前两项的和等于后一项，用递归描述：f(n）= f(n-1）+ f(n-2），n > 2 且是整数；
递归
// 获取第 n 项的斐波那契数
public static int f(int n) {
// 前一项
if (n < 2) {
// 如果 n 是第 1 项，返回 1，否则返回 0
return n == 1 ? 1 : 0;
}
return f(n - 1) + f(n - 2);
}
循环
if (n < 2) {
return n == 1 ? 1 : 0;
}
int n0 = 0;
int n1 = 1;
for (int i = 2; i <= n; i++) {
int n2 = n0 + n1;
// 后移一位
n0 = n1;
n1 = n2;
}
return n2;
循环比递归效率高些。
8.3.2 斐波那契查找Fibonacci Search：前提是有序数组。
{0，1，1，2，3，5，8，13，21，34 …}，0 是第 0 项。
引子：数组长度为 n，下标从 0 到 n - 1，总范围：[0, n - 1]；从 start 开始取出 8 个元素，则它们的下标分别为 start、start + 1、start + 2、… start + 7 即 [start, start + 7]。
引子 2：记第 k 项的斐波那契数为 f(k），则 k > 2 时，有 f(k）= f(k - 1）+ f(k - 2）
设 k 为正整数，从个数为 f(k）- 1 的元素集合中寻找 num 的下标，记最左边的元素下标 start，则查找范围为 [start, start + f(k）- 2]，取 mid = start + f(k - 1）- 1，将其分割成两个部分，左边范围：[start, mid - 1] 即 [start, start + f(k - 1）- 2]；右边范围：[mid + 1, f(k）- 2] 即 [start + f(k - 1）, start + f(k）- 2]；
左边部分的元素个数为 (start + f(k - 1）- 2）- start + 1 = f(k - 1）- 1；
右边部分的元素个数为 (start + f(k）- 2）- (start + f(k - 1））+ 1 = f(k）- f(k - 1）- 1 = f(k - 2）- 1；
无论是左部分还是右部分，都可以重复上述过程，如从元素个数为 f(m）- 1 的集合中寻找 num 的下标，记最左边的元素下标为 start … （左半部分 m = k - 1，右半部分 m = k - 2）
直到 arr[mid] = num 为止。
需要注意的是数组长度 n 并不一定等于 f(k）- 1，这需要将其扩容至 f(k）- 1（保证 f(k）- 1 要大于等于 n）；多出来的部分补最大值 arr[n - 1]，以保证是有序数组，所以如果查到的 num 的下标大于等于 n，则 arr[num] = arr[n - 1]，返回 n - 1 即可。
public static int fibonacciSearch(int[] arr, int num) {
int n = arr.length;
int start = 0;
int end = n - 1;
// 如果 f(k) - 1 < n，则 k++，一直到 f(k) - 1 >= n 为止
int k = 0;
while (f(k) - 1 < n) {
k++;
}
int[] temp = new int[f(k) - 1];
// 前 n 个元素与 arr 一致
for (int i = 0; i < n; i++) {
temp[i] = arr[i];
}
// 多出来的部分补 arr[n - 1]（下标大于等于 n 的元素都为 arr[n - 1]）
for (int i = n; i < f(k) - 1; i++) {
temp[i] = arr[n - 1];
}
while (start <= end) {
int mid = start + f(k - 1) - 1;
int midVal = temp[mid];
// num 在左半部分，k 应减一
if (num < midVal) {
end = mid - 1;
k--;
// num 在右半部分，k 应减二
} else if (num > midVal) {
start = mid + 1;
k -= 2;
// arr[mid] = num
} else {
// mid < n
if (mid < n) {
return mid;
// mid >= n
} else {
return n - 1;
}
}
}
return -1;
}
f(k）可以使用备好的斐波那契数组 f[k] 取代。
这种六四分的方式，如果要查找的元素偏右边一些，当然会比二分查找效率高；否则还不如二分查找。
8.x 总结回顾一片朦胧选二分，分布均匀选插值，偏右选黄金分割。
8.y 脑海练习8.1 编写方法返回长度为 n 的斐波那契数组。（包括 0）
参考答案 第八章答案8.1 编写方法返回长度为 n 的斐波那契数组。（包括 0）
public static int[] fibonacciArr(int n) {
if (n < 2) {
return new int[]{0};
} else if (n == 2) {
return new int[]{0, 1};
}
int[] f = new int[n];
f[0] = 0;
f[1] = 1;
for (int i = 2; i < n; i++) {
f[i] = f[i - 1] + f[i - 2];
}
return f;
}
