一、常见的查找分类
1. 顺序(线性)查找
2. 二分查找/折半查找
3. 插值查找
4. 斐波那契查找(黄金分割点查找)
——- 根据黄金分割点的值进行对比, 二分法是对照位于50%处的点, 斐波那契数列是对照位于61.8%位置的点
二、顺序(线性)查找
1. 逻辑思维
2. 代码实现
public static int sequenceSearchFun(int[] arr, int value) {
// 线性查找是逐一比对
int i=0;
for (i=0; i < arr.length; i++) {
if (arr[i] == value) {
return i;
}
}
return i;
}
三、二分查找/折半查找
1. 逻辑思维
原数组有序,现在需要通过二分法找到目标元素的下标
二分查找的思路分析
1. 首先确定该数组的中间的下标
mid = (left + right) / 2
2. 然后让需要查找的数 findVal 和 arr[mid] 比较
2. 1 findVal > arr[mid] , 说明你要查找的数在mid 的右边, 因此需要递归的向右查找
2.2 findVal < arr[mid], 说明你要查找的数在mid 的左边, 因此需要递归的向左查找
2.3 findVal == arr[mid] 说明找到,就返回
//什么时候我们需要结束递归.
1) 找到就结束递归
2)递归完整个数组,仍然没有找到findVal ,也需要结束递归 当 left > right 就需要退出
2. 代码实现
public static int binarySearchFun(int[] arr,int left,int right,int findVal){
if(left>right){
return -1;
}
int mid = (left+right)/2;
int midVal = arr[mid];
if(midVal<findVal){
//需要向右递归
return binarySearchFun(arr, mid, right, findVal);
}else if(midVal>findVal){
return binarySearchFun(arr, left, mid-1, findVal);
}else {
return mid;
}
}
3. 升级代码
当数组中有重复的值时,找到所有符合条件的下标
public static List<Integer> binarySearchFun(int[] arr,int left,int right,int findVal){
List<Integer> resList = new ArrayList<Integer>();
if(left>right){
return resList;
}
int mid = (left+right)/2;
int midVal = arr[mid];
if(midVal<findVal){
//需要向右递归
return binarySearchFun(arr, mid, right, findVal);
}else if(midVal>findVal){
return binarySearchFun(arr, left, mid-1, findVal);
}else {
// 当数组中有多个值符合要求时,找到后先不要立即返回,而是继续向左和向有扫描
int temp = mid-1;
while (left >= 0 && arr[mid] == findVal) {
resList.add(temp);
temp--;
}
resList.add(mid);
temp = mid+1;
while (left >= 0 && arr[mid] == findVal) {
resList.add(temp);
temp--;
}
return resList;
}
}
四、插值查找
1. 逻辑思维
2. 代码实现
public static int insertValueFun(int[] arr,int left, int right, int findVal){
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 insertValueFun(arr, mid+1, right, findVal);
}else if(findVal<midVal){
return insertValueFun(arr, left, mid, findVal);
}else {
return mid;
}
}
3. 注意事项
![image.png](https://cdn.nlark.com/yuque/0/2021/png/22435741/1640875839375-4cc3149f-a578-452c-bdca-72210a4b9127.png#clientId=udec2da87-a861-4&from=paste&height=195&id=u997b31cc&margin=%5Bobject%20Object%5D&name=image.png&originHeight=228&originWidth=1198&originalType=binary&ratio=1&size=37391&status=done&style=none&taskId=u3e9a35d0-31bb-453a-9598-52d64159fd4&width=1024)
五、斐波那契(黄金分割法)—-黄金分割点
1. 逻辑思维
注意:下述推导,不是依靠具体某个点的数值,而是依靠长度,即:F[K]-1 代表整体长度
2. 代码实现——查找算法
**请对一个有序数组进行斐波那契查找 {1,8, 10, 89, 1000, 1234} ,输入一个数看看该数组是否存在此数,并且求出下标,如果没有就提示"没有这个数"。eg: findVal = 1,return index=0; findVal=1234, return index=5;**
package com.atguigu.search;
import sun.security.util.Length;
import java.util.Arrays;
public class FibonacciSearchDemo {
public static void main(String[] args) {
System.out.println(Arrays.toString(fib()));
}
// 需要使用到Fibonacci数列
public static int[] fib(){
int[] f = new int[20]; //20个元素
f[0]=1;
f[1]=1;
for (int i = 2; i < f.length; i++) {
f[i]=f[i-1]+f[i-2];
}
return f;
}
/**
* 非递归方法
* @param arr
* @param key 要查找的数
* @return 被查找数的下标
*/
public static int fibonacciSearchFun(int[] arr, int key){
int low = 0;
int high = arr.length-1;
int k = 0; // 表示斐波那契数列分割数值的下标
int mid = 0; // 存放mid值
int[] f = fib();
// 获取到斐波那契数列分割数值下标
// 该数列总长度: length =f[k]-1
while(high>f[k]-1){
// 当没有找到时,k++
k++;
}
// 因为f[k]值可能大于a的长度,因此需要我们使用Arrays类,构造一个新的数组
// 不足的后面部分会使用0填充
int[] temp = Arrays.copyOf(arr, f[k]);
// 实际上需要使用arr数组的最后的数对新数组剩余的部分填充
for (int i = high+1; i < temp.length; i++) {
temp[i]=arr[high];
}
//循环处理进行查找
while(low<=high){
mid = low+f[k-1]-1; // mid是下标, low也是下标, f[k-1]代表长度
if(key<temp[mid]){
// 向左边查找
// 说明:全部元素=前面元素+后面元素
// f[k]=f[k-1] + f[k-2]
// 前面有f[k-1]个元素,所以可以拆分为: f[k-1]=f[k-2]+f[k-3]
// 即在f[k-1]前面继续查找
high=mid-1;
k--;
}else if(key>temp[mid]){
// 向右边查找 f[k-1]=f[k-3]+f[k-4]
low = mid+1;
k -=2;
} else {
// 找到了
// 需要确定返回的是哪个下标
if(mid<=high){
return mid;
}else {
return high;
}
}
}
return -1;
}
}
**