一、常见的查找分类
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. 注意事项
五、斐波那契（黄金分割法）—-黄金分割点
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;
}
}
**
若有收获，就点个赞吧
0 人点赞
