一 顺序查找
没什么好说的，就是依次查找。对数组是否有序没有要求
/**
* 这里我们实现的线性查找是找到一个满足条件的值，就返回
* @param arr
* @param value
* @return
*/
public static int seqSearch(int[] arr, int value) {
// 线性查找是逐一比对，发现有相同值，就返回下标
for (int i = 0; i < arr.length; i++) {
if(arr[i] == value) {
return i;
}
}
return -1;
}
二 二分查找
前提：数组有序
2.1 思路
image.png
分析可得：
如果目标值不在数组中，则必然会遇到left下标=right下标还找不到目标值的场景。（假设此时下标为n）
接下就是两种情况
- 目标值>arr[n];则right+1>left
- 目标值<arr[n];则left-1<right
2.2 代码实现
此时是数组从小到大的找法，否则反着来即可
/**
*
* @param arr
* 数组
* @param left
* 左边的索引
* @param right
* 右边的索引
* @param findVal
* 要查找的值
* @return 如果找到就返回下标，如果没有找到，就返回 -1
*/
public static int binarySearch(int[] arr, int left, int right, int findVal) {
// 当 left > right 时，说明递归整个数组，但是没有找到
if (left > right) {
return -1;
}
int mid = (left + right) / 2;
int midVal = arr[mid];
if (findVal > midVal) { // 向 右递归
return binarySearch(arr, mid + 1, right, findVal);
} else if (findVal < midVal) { // 向左递归
return binarySearch(arr, left, mid - 1, findVal);
} else {
return mid;
}
}
三 插值查找
3.1 思想
image.png
总结：和二分查找的区别只是mid的计算方式不同
3.2 代码实现
/**
*
* @param arr 数组
* @param left 左边索引
* @param right 右边索引
* @param findVal 查找值
* @return 如果找到，就返回对应的下标，如果没有找到，返回-1
*/
public static int insertValueSearch(int[] arr, int left, int right, int findVal) {
System.out.println("插值查找次数~~");
//注意：findVal < arr[0] 和 findVal > arr[arr.length - 1] 必须需要
//否则我们得到的 mid 可能越界
if (left > right || findVal < arr[0] || findVal > arr[arr.length - 1]) {
return -1;
}
// 求出mid, 自适应
int mid = left + (right - left) * (findVal - arr[left]) / (arr[right] - arr[left]);
int midVal = arr[mid];
if (findVal > midVal) { // 说明应该向右边递归
return insertValueSearch(arr, mid + 1, right, findVal);
} else if (findVal < midVal) { // 说明向左递归查找
return insertValueSearch(arr, left, mid - 1, findVal);
} else {
return mid;
}
}
}
四 斐波那契(黄金分割法)查找算法
4.1 基本思想
- 黄金分割点是指把一条线段分割为两部分，使其中一部分与全长之比等于另一部分与这部分之比。取其前三位 数字的近似值是 0.618。由于按此比例设计的造型十分美丽，因此称为黄金分割，也称为中外比。这是一个神 奇的数字，会带来意向不大的效果。
- 斐波那契数列 {1, 1, 2, 3, 5, 8, 13, 21, 34, 55 } 发现斐波那契数列的两个相邻数 的比例，无限接近 黄金分割值 0.618
参考：
- https://www.cnblogs.com/yongh/p/9232742.html#_label1_2
- https://blog.csdn.net/luochoudan/article/details/51629338
4.2 小结
image.png
- 斐波那契数列中的
值表示的是数组中参与寻找的元素个数.所以（F[k]-1）=（F[k-1]-1）+（F[k-2]-1）+1我的解读是:对于一个元素个数是（F[k]-1）的数组，它的比较点应该是在前（F[k-1]-1）个元素后面，后（F[k-2]-1）个元素前面。
这样的话我们就可以马上找到比较点的位置了。 - 之后不采用遍历，直接
k-1,k-2是为什么？
由上面的图可得，假设mid比寻找的值小。则应该去前面（F[k-1]-1）（假设k-1=z）个元素中找，上面的k都是代指。则新的比较点就是F[z-1]-1的个元素后面。 - 但有时候我们的数组长度很难恰好等于F[k]-1，这时只需要将原数组扩容（扩容到第一个比他大的F[k]）.新的元素值全是arr[length-1]
