目录
一：查找算法介绍
二：二分查找
三：插值查找
四：斐波那契查找
一：查找算法介绍
在Java中，我们常用的查找有四种：
- 顺序（线性）查找
- 二分查找/折半查找
- 插值查找
- 斐波那契查找
二：二分查找
2.1 思想：
有序的序列，每次都是以序列的中间位置的数来与待查找的关键字进行比较，每次缩小一半的查找范围，直到匹配成功。
一个情景：将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。
2.2 思路分析：
1.首先确定该数组的中间的下标，mid=(left+right)/2;
2.然后让需要查找的数findVal和arr[mid]比较
2.1 findVal>arr[mid]，说明你要查找的数在mid的右边，因此需要递归的向右查找
2.2 findVal
2.3 findVal==arr[mid],说明找到，就返回。
//什么时候我们需要结束递归
1）找到要搜索的数字就结束递归
2）递归完整个数组，仍然没有找到findVal,也需要结束递归，当left>right就需要退出。
2.3 二分查找代码实现：
package BinarySearch;
import java.util.ArrayList;
public class BinarySearchDemo {
public static void main(String[] args) {
int arr[]={1,8,10,89,1000,1000,1234};
ArrayList list=BinarySearch(arr,0,arr.length-1,1000);
System.out.println(list);
}
public static ArrayList BinarySearch(int[] arr,int left,int right,int findVal){
if(left>right){
return new ArrayList<>();
}
int mid=(left+right)/2;
if(findVal>arr[mid]){//向右递归
return BinarySearch(arr,mid+1,right,findVal);
}else if(findVal resIndexList=new ArrayList<>();
//向mid索引值的左边扫描，将所有满足条件的下标加入集合
int temp=mid-1;
while (temp>=0&&arr[temp]==findVal){
resIndexList.add(temp--);
}
//再将满足条件的中间的下标加入到集合中
resIndexList.add(mid);
//向mid索引值的右边扫描，将所有满足条件的下标加入集合
temp=mid+1;
while (temp<=right&&arr[temp]==findVal){
resIndexList.add(temp++);
}
return resIndexList;
}
}
}
三：插值查找
3.1 插值查找的思想：
与二分查找类似，不同的是求mid指针的公式不同
其mid=left + (right - left) * (findVal - arr[left]) / (arr[right] - arr[left]);
对于数据量较大，关键字分布比较均匀的查找表来书，该方法速度快
在关键字分布不均匀的情况下，该方法不一定比二分查找好
3.2 代码实现：
public class insertValueSearch {
public static void main(String[] args) {
int[] arr=new int[100];
for(int i=0;i<100;i++){
arr[i]=i+1;
}
int ans=insertValueSearch(arr,0,arr.length-1,110);
System.out.println(ans);
}
//编写插值查找算法(数组有序)
public static int insertValueSearch(int[] arr,int left,int right,int findVal){
//注意：findValarr[arr.length-1]必须需要，防止mid越界
if(left>right||findValarr[arr.length-1]){
return -1;
}
//求出mid,自适应
int mid=left+(right-left)*(findVal-arr[left])/(arr[right]-arr[left]);
int midVal=arr[mid];
if(midValfindVal){//向左递归
return insertValueSearch(arr,left,mid-1,findVal);
}else {
return mid;
}
}
}
3.3 插值查找注意事项：
对于数据量较大，关键字分布比较均匀的查找表来说，采用插值查找，速度较快。
关键字分布不均匀的情况下，该方法不一定比折半查找要好。
四：斐波那契查找
4.1 思想：
斐波那契搜索就是在二分查找的基础上根据斐波那契数列进行分割的。在斐波那契数列找一个等于略大于查找表中元素个数的数F[n]， 将原查找表扩展为长度为F[n](如果要补充元素，则补充重复最后一个元素，直到满足F[n]个元素)，完成后进行斐波那契分割，即F[n]个元素分割为前半部分F[n-1]个元素，后半部分F[n-2]个元素，找出要查找的元素在那一部分并递归，直到找到。
4.2 原理分析：
斐波那契查找原理与前两种相似，仅仅改变了中间结点（mid）的位置，mid不再是中间或插值得到，而是位于黄金分割点附近，即mid=low+F(k-1)-1（F代表斐波那契数列）
重要公式：mid=low+F[k-1]-1
适用条件： 采用顺序存储结构的有序表
理解：mid在黄金分割点附近，
F(k-1)-1:是由斐波那契数列的“F[k]=F[k-1]+F[k-2]”,F[k]-1=(F[k-1]-1)+(F[k-2]-1)+1,则若顺序表的长度为：F[k]-1,则可分成F[k-1]-1和F[k-2]-1两段，中间位置就为：mid=low+F[k-1]-1）（注）：顺序表长度n不一定刚好等于F[k]-1,所以需要将原来的顺序表长度n增加至F[k]-1。这里的k值只要能使得F[k]-1恰好大于或等于n即可，由以下代码得到，顺序表长度增加后，新增的位置（从n+1到F[k]-1位置），都赋为n位置的值即可。
while(n>fib(k)-1){
k++;
}
4.3 代码实现：
import java.util.Arrays;
public class FibonacciSearch {
//因为后面我们mid=low+F(K-1)-1,需要使用到斐波那契数组，因此我们需要先获取到一个斐波那契数组
//非递归方法
public static int maxsize=20;
public static int[] fib(){
int[] f=new int[maxsize];
f[0]=1;
f[1]=1;
for(int i=2;if[k]-1){
k++;
}
//因为f[k]值可能大于a的长度，因此我们需要使用Arrays类，构造一个新的数组，并指向a[]
//不足的部分会使用0填充
int[] temp= Arrays.copyOf(a,f[k]);
//但实际上需求使用a数组最后的数填充temp
//举例：
//int[] temp={1,8,10,89,1000,1234,0,0,0} ====> int[] arr={1,8,10,89,1000,1234,1234,1234,1234}
for(int i=high+1;itemp[mid]){//我们应该继续向数组的后面查找（后面）
low=mid+1;
//为什么是k-=2；
//说明
//1.全部数组=前面的元素+后面的元素
//2.f[k]=f[k-1]+f[k-2]
//3.因为后面有f[k-2]个元素，所以可以继续拆分f[k-2]=f[k-3]+f[k-4]
//4.即在f[k-2]的前面进行查找k-=2
//5.下次循环mid=f[k-1-2]-1;
k-=2;
}else {//找到元素，即key==temp[mid],因为mid可能大于high（前面已经将数组扩容了）
//需要确定，返回的是哪一个下标
if(mid<=high){
return mid;
}else {
return high;
}
}
}
return -1;
}
}
