查找
1. 二分查找
二分查找(折半查找)必须采用顺序存储结构，并且必须按关键字大小有序排列。
二分查找求mid公式：
二分查找的时间复杂度：
递归实现二分查找-：
// 二分查找(递归)
public static int binarySearch(int[] container, int fromIndex, int toIndex, int key) {
if (fromIndex > toIndex)
// 没找到，返回负数
return -(fromIndex + 1);
int mid = (fromIndex + toIndex) >> 1;
int midVal = container[mid];
if (midVal < key)
return binarySearch(container, mid + 1, toIndex, key);
else if (midVal > key)
return binarySearch(container, fromIndex, mid - 1, key);
else
// 找到了，返回索引
return mid;
}
非递归实现二分查找*：
// 二分查找(非递归)
public static int binarySearch(int[] container, int key) {
int low = 0;
int high = container.length - 1;
while (low <= high) {
int mid = (low + high) >> 1;
int midVal = container[mid];
if (midVal < key)
low = mid + 1;
else if (midVal > key)
high = mid - 1;
else
// 找到了，返回索引
return mid;
}
// 没找到，返回负数
return -(low + 1);
}
2. 插值查找
插值查找基于二分查找，将查找点的选择改进为自适应选择，提高查找效率。
插值查找求mid公式：
插值查找的时间复杂度：
当关键字分布较均匀时，采用插值查找速度较快；否则，插值查找不一定比二分查找速度快。
插值查找代码实现：修改二分查找的mid和判断条件
// 插值查找(修改二分查找的mid和判断条件)
public static int interpolationSearch(int[] container, int key) {
int low = 0;
int high = container.length - 1;
// key若不在[low, high]区间内，则找不到，
// 而且也防止了因key过大或过小，导致mid过大或过小，而造成数组越界
while (low <= high && container[low] <= key && key <= container[high]) {
int mid = low + (key - container[low]) / (container[high] - container[low]) * (high - low);
int midVal = container[mid];
if (midVal < key)
low = mid + 1;
else if (midVal > key)
high = mid - 1;
else
// 找到了，返回索引
return mid;
}
// 没找到，返回负数
return -(low + 1);
}
3. 斐波那契查找
斐波那契搜索也是二分查找的一种提升算法，通过运用黄金比例的概念在数列中选择查找点进行查找，提高查找效率。
黄金比例又称黄金分割，是指将整体一分为二，较大部分与较小部分之比等于整体与较大部分之比，其比值约为1:0.618或1.618:1。
随着斐波那契数列的递增，前后两个数的比值会越来越接近0.618；斐波那契数列如下：
由上面公式可知：只要顺序表的长度为，就可以将该顺序表划分成
三段，但顺序表的长度可能小于
，因此需要将顺序表的长度增加至
。
斐波那契查找求mid公式：
斐波那契查找的时间复杂度：；与折半查找相比，斐波那契查找的优点是它只涉及加法和减法运算，而不用除法
斐波那契搜索是一种函数估值次数最少的最优搜索方法
插值查找代码实现：结合上面分析来理解
// 斐波那契查找
public static int fibonacciSearch(int[] container, int key) {
int low = 0;
int high = container.length - 1;
// 获取一个斐波那契数列
List<Integer> fibonacci = getFibonacciSequence(container.length);
// n代表第几个斐波那契数
int n = fibonacci.size() - 1;
// 将数组扩容至F[n]-1
int[] expanded = Arrays.copyOf(container, fibonacci.get(n) - 1);
// 用原容器最后一个数来填充多出来的空间
for (int i = container.length; i < expanded.length; i++) {
expanded[i] = container[container.length - 1];
}
// 每一轮的搜索区间长度为F[n]-1，就可以分割
while (low <= high) {
int mid = low + (fibonacci.get(n - 1) - 1);
int midVal = expanded[mid];
if (midVal < key) {
low = mid + 1;
// 下一轮在右边区域找，其长度为F[n-2]-1，因此让n变成n-2
n -= 2;
} else if (midVal > key) {
high = mid - 1;
// 下一轮在左边区域找，其长度为F[n-1]-1，因此让n变成n-1
n -= 1;
} else {
// 如果找到的是原容器中的元素，直接返回索引
if (mid <= high)
return mid;
else
// 如果找到的是填充值，则返回原容器最后一个元素的索引
return high;
}
}
// 没找到，返回负数
return -1;
}
// 获取一个斐波那契数列，有且仅有(最后一个斐波那契数-1)大于等于容器容量
private static List<Integer> getFibonacciSequence(int length) {
ArrayList<Integer> fibonacci = new ArrayList<>();
fibonacci.add(1);
fibonacci.add(1);
int last = 1;
while (fibonacci.get(last) - 1 < length) {
// 给斐波那契数列中添加一个数
fibonacci.add(fibonacci.get(last) + fibonacci.get(last - 1));
last++;
}
return fibonacci;
}
