java常见的查找算法

1、线性查找

2、二分法查找

3、插值查找

4、斐波那契查找

线性查找又称顺序查找，是最简单的查找方法查找，是一种最简单的查找方法。其原理就是循环遍历数组去查找的所要的元素，找到了就返回下标，没有就返回-1,实用于有序无序

public class LinearSearch {
	public static void main(String[]args){
        //创建数组
		String[]arr = new String[]{"AA","BB","CC","DD"};
		String dest = "BB";       //所需要查找的元素
		boolean isFlag = true;
        
        //遍历数组，查找所需元素，找到后返回其下标
		for(int i= 0; i

二分法查找又称折半查找，其思路如下

1. 首先，从数组的中间元素开始搜索，如果该元素正好是目标元素，则结束进程，返回所查找元素的下标，否则执行下一步。
2. 如果目标元素大于或小于中间元素，则在数组大于或小于中间元素的那一半区域查找，然后重复上一步骤的操作，直到找到所需元素，返回其下标。
3. 如果某一步数组为空，则表示找不到目标元素
   
   二分法查找算法的数组必须是有序的（局限性），在使用二分法查前，须将数组进行排序

public class BinarySearch {
	public static void main(String[]args){
        //创建数组
		int[]arr = new int[]{-98,-34,2,34,54,66,79,105};
		int dest = -34;        //所要查找的元素
		int head = 0;    //定义初始的首索引
		int end = arr.length - 1;    //定义初始的末索引
		boolean isFlag = true;
		while(head<=end)
		{
			int middle = (head+end)/2;
			if(dest == arr[middle]){
				System.out.println("找到指定元素，位置为" + middle);
				isFlag = false;
				break;
			}else if(arr[middle]>dest){
				end = middle -1;
			}else{
				head = middle +1;
			}
		}
		if(isFlag){
			System.out.println("未找到指定元素");
		}
	}
}

1. 插值查找算法类似于二分查找，不同的是插值查找每次从自适应mid处开始查找。
2. 将折半查找中的求mid 索引的公式 , low 表示左边索引left, high表示右边索引right. key 就是上面代码中的  findVal。其公式如下
3. 思路：与二分一样， findValarr[arr.length-1])是必须要的，否则可能会越界。

public class InterpolationSearch {

    public static void main(String[] args) {
        int[] array = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        int index = interpolation(array, 0, array.length - 1, 10);
        if (index != -1) {
            System.out.println("index = " + index);
        } else {
            System.out.println("没有找到~~~");
        }
    }

    public static int interpolation(int[] array, int low, int high, int value) {
        if(low > high || value < array[low] || value > array[high]) {
            return -1;
        }
        while (low <= high) {
            int mid = low + (high - low) * (value - array[low]) / (array[high] - array[low]);
            int midValue = array[mid];
            if (value < midValue) {
                high = mid - 1;
            } else if (value > midValue) {
                low = mid + 1;
            } else {
                return mid;
            }
        }
        return -1;
    }
}

斐波那契查找又称黄金比例查找法，类似于二分法查找，它们的不同之处在于，斐波那契查找将查找点的对半选择改进为黄金分割点选择

让我们了解一下斐波那契数列

        斐波那契数列（Fibonacci sequence），又称黄金分割数列，因数学家莱昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”。

        斐波那契数列指的是这样一个数列：

        0，1，1，2，3，5，8，13，21，34，55.......

        它的规律是：这个数列从第 3 项开始，每一项都等于前两项之和。

        在数学上，斐波那契数列以如下被以递推的方法定义：F(0)=0，F(1)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 2，n ∈ N*），显然，斐波那契数列是一个线性递推数列

思路如下

斐波那契查找的整个过程可以分为：

• 构建斐波那契数列；
• 计算数组长度对应的斐波那契数列元素个数；
• 对数组进行填充；
• 循环进行区间分割，查找中间值；
• 判断中间值和目标值的关系，确定更新策略

public class FibonacciSearch {
	
	public static int maxSize=20;
	public static void main(String[] args) {
		//定义初始数组
		int[] arr= {1,8,10,89,1000,1234};
		int findVal=10;
		System.out.println(fabnacciSearch(arr, findVal));
	}
	
	//构建斐波那契数列
	public static int[] Fabonacci() {
		int[] f=new int[maxSize];
		f[0]=1;
		f[1]=1;
		for(int i=2;if[k]-1) {
			k++;
		}
		//因为f[k]值可能大于数组arr的长度，因此需要使用Arrays类，构造一个新的数组，并指向arr[]
		//不足的部分会使用0填充
		int[] temp=Arrays.copyOf(arr, f[k]);
		//实际上需求使用a数组最后的数填充temp
		for(int i=high+1;itemp[mid]) {  //向右查找
				low=mid+1;
				k-=2;   //f[k]=f[k-1]+f[k-2]  mid左边是f[k-1]，右边是f[k-2]
			}else if(findValmid) {  //因为之前的temp数组填充了arr[high]
					return mid;
				}else {
					return high;
				}
			}
		}
		return -1;
		
	}

}

对n=F(K)-1的理解

为了格式上的统一，以方便递归或者循环程序的编写。表中的数据是F(k)-1个，使用mid值进行分割又用掉一个，那么剩下F(k)-2个。正好分给两个子序列，每个子序列的个数分别是F(k-1)-1与F(k-2)-1个，格式上与之前是统一的。不然的话，每个子序列的元素个数有可能是F(k-1)，F(k-1)-1，F(k-2)，F(k-2)-1个，写程序会非常麻烦