查找算法
- 静态查找和动态查找：静态或者动态都是针对查找表而言的。动态表指查找过程中有删除和插入操作的表
- 无序查找和有序查找：待查找的查找表是否有序
- 平均查找长度 ASL（
Average Search Length）：需和指定 key 进行比较的关键字的个数的期望值，称为查找算法在查找成功时的平均查找长度- 对于含有 n 个数据元素的查找表，查找成功的平均查找长度：
ASL = Pi * Ci的和；Pi：查找表中第 i 个数据元素的概率；Ci：找到第 i 个数据元素时已经比较过的次数
一、二分查找
1. 二分查找基本思想
元素必须是有序的，如果是无序的则要先进行排序操作。二分查找也称折半查找，用给定值 k 先与中间结点的关键字比较，中间结点把线形表分成两个子表，若相等则查找成功；若不相等，再根据 k 与该中间结点关键字的比较结果确定下一步查找哪个子表，这样递归进行，直到查找到或查找结束发现表中没有这样的结点。折半查找的前提条件是需要有序表顺序存储，对于静态查找表，一次排序后不再变化，折半查找能得到不错的效率。但对于需要频繁执行插入或删除操作的数据集来说，维护有序的排序会带来不小的工作量，那就不建议使用
2. 二分查找算法 java 代码实现
/**
* 二分查找法：递归
*
* @param array 数组
* @param begin 左索引，初始化为 0
* @param end 右索引，初始化为 array.length - 1
* @param target 目标数
* @return 在 array 中找到 target 则返回其最下标，未找到返回 -1
*/
public Integer binarySearch(int[] array, int begin, int end, int target) {
if (begin > end) {
return -1;
}
int mid = (begin + end) / 2;
// 目标值比中间值大，在后半区间递归查找
if (target > array[mid]) {
return binarySearch(array, mid + 1, end, target);
} else if (target < array[mid]) {
return binarySearch(array, begin, mid - 1, target);
} else {
return mid;
}
}
二、插值查找算法
1. 插值查找基本思想
基于二分查找算法，将查找点的选择改进为自适应选择
int mid = begin + (end - begin) * (target - array[begin]) / (array[end] - array[begin]);，可以提高查找效率。当然，差值查找也属于有序查找。对于表长较大，而关键字分布又比较均匀的查找表来说，插值查找算法的平均性能比折半查找要好的多。反之，数组中如果分布非常不均匀，那么插值查找未必是很合适的选择
2. 插值查找算法 java 代码实现
/**
* 插值查找算法：递归
*
* @param array 数组
* @param begin 左索引，初始化为 0
* @param end 右索引，初始化为 array.length - 1
* @param target 目标数
* @return 在 array 中找到 target 则返回其下标，未找到返回 -1
*/
public int interpolatedSearch(int[] array, int begin, int end, int target) {
if (begin > end || target < array[0] || target > array[array.length - 1]) {
return -1;
}
int mid = begin + (end - begin) * (target - array[begin]) / (array[end] - array[begin]);
// 目标值比中间值大，在后半区间递归查找
if (target > array[mid]) {
return interpolatedSearch(array, mid + 1, end, target);
} else if (target < array[mid]) {
return interpolatedSearch(array, begin, mid - 1, target);
} else {
return mid;
}
}
三、斐波那契查找算法
1. 斐波那契查找基本思想
- 在介绍斐波那契查找算法之前，先介绍一下很它紧密相连的一个概念_黄金分割。黄金比例又称黄金分割，是指事物各部分间一定的数学比例关系，即将整体一分为二，较大部分与较小部分之比等于整体与较大部分之比，其比值约为
1:0.618或1.618:1。0.618被公认为最具有审美意义的比例数字，这个数值的作用不仅仅体现在诸如绘画、雕塑、音乐、建筑等艺术领域，而且在管理、工程设计等方面也有着不可忽视的作用。因此被称为黄金分割。斐波那契数列1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89…….（从第三个数开始，后边每一个数都是前两个数的和）。然后我们会发现，随着斐波那契数列的递增，前后两个数的比值会越来越接近0.618，利用这个特性，我们就可以将黄金比例运用到查找技术中- 相对于折半查找，一般将待比较的
key值与第mid=（low+high）/ 2位置的元素比较，斐波那契搜索也是二分查找的一种提升算法，通过运用黄金比例的概念在数列中选择查找点进行查找，提高查找效率。同样地，斐波那契查找也属于一种有序查找算法- 斐波那契查找与折半查找很相似，他是根据斐波那契序列的特点对有序表进行分割的。他要求开始表中记录的个数为某个斐波那契数小
1，即n = F(k) - 1；开始将k值与第F(k-1)位置的记录进行比较(即mid = low + F(k-1) - 1)，比较结果也分为三种：
3.1 相等，则mid位置的元素即为所求
3.2 >，则low=mid+1，k-=2 ；说明：low=mid+1说明待查找的元素在[mid+1,high]范围内，k-=2说明范围[mid+1,high]内的元素个数为n-(F(k-1))=Fk-1-F(k-1)=Fk-F(k-1)-1=F(k-2)-1个，所以可以递归的应用斐波那契查找
<，则high=mid-1，k-=1；说明：low=mid+1说明待查找的元素在[low,mid-1]范围内，k-=1说明范围[low,mid-1]内的元素个数为F(k-1)-1个，所以可以递归的应用斐波那契查找- 在最坏情况下，斐波那契查找的时间复杂度还是O(log2n)，且其期望复杂度也为O(log2n)，但是与折半查找相比，斐波那契查找的优点是它只涉及加法和减法运算，而不用除法，而除法比加减法要占用更多的时间，因此，斐波那契查找的运行时间理论上比折半查找小，但是还是得视具体情况而定
2. 斐波那契查找算法 java 代码实现
/**
* 斐波那契查找
*
* @param array 有序数组
* @param key 需要查找的值
* @return key 在 array 中的位置，不存在则返回 -1
*/
public int fibonacciSearch(int[] array, int key) {
int low = 0;
int n = array.length;
int high = n - 1;
int[] fib = fibonacci(20);
int k = 0;
// 计算 n 位于斐波那契数列的位置
while (n > fib[k] - 1) {
++k;
}
// 将数组 array 扩展到 F[k] - 1 的长度
int[] temp = Arrays.copyOf(array, fib[k] - 1);
// 用 array 的最后一个填充新扩充的数组
for (int i = n; i < fib[k] - 1; i++) {
temp[i] = array[high];
}
while (low <= high) {
int mid = low + fib[k - 1] - 1;
if (key < temp[mid]) {
// 在前半部分查找
high = mid - 1;
// // F[k] = F[k-1] + F[k-2]
k--;
} else if (key > temp[mid]) {
// 在后半部分查找
low = mid + 1;
// F[k] = F[k-1] + F[k-2]
k -= 2;
} else {
if (mid < n) {
return mid;
} else {
// 若 mid>=n 则说明是扩展的数值,返回 high
return high;
}
}
}
return -1;
}
/**
* 生成指定元素个数的斐波那契数列
*
* @return 斐波那契数列
*/
public int[] fibonacci(int size) {
int[] fib = new int[size];
fib[0] = 1;
fib[1] = 1;
for (int i = 2; i < size; i++) {
fib[i] = fib[i - 2] + fib[i - 1];
}
return fib;
}
