查找算法

• 顺序查找

• 二分查找

• 插值查找

• 斐波那契查找

顺序查找

按照数组排列顺序进行指定数据查找，对数组无要求

缺点：效率较低

//顺序查找
public class SeqSearch
{
    public static void main(String[] args)
    {
        int arr[]= {1,3,2,6,5,4,9,7};
        System.out.println(seqSearch(arr, 6));
    }
    //arr查找数组，value指定的查找数据
    public static int seqSearch(int arr[],int value) {
        for(int i=0;i<arr.length;i++) {
            if(arr[i]==value) {
                //找到
                return i;
            }
        }
        return -1;
    }
}

二分查找

要求：数组必须为有序数组

方法：将查找值与中中间值比较，大于中间值则在中间值与右边值中间找，小于则在左边值和中间值中间找，重复操作，得到查找数据的位置

//二分查找
public class BinarySearch
{
    public static void main(String[] args)
    {
        int arr[]= {1,2,4,6,9,12,15,44};
        System.out.println(binarySearch(arr, 0, arr.length-1, 222));
    }
    
    //arr[]目标值所在数组，value目标值
    //left左边索引，right右边索引
    public static int binarySearch(int arr[],int left,int right,int value) {
        //没找到
        if(left>right) {
            return -1;
        }
        int mid=(left+right)/2;
        if(arr[mid]<value) {
            //目标值在中间值-右边索引
            return binarySearch(arr, mid+1, right, value);
        }else if(arr[mid]>value){
            //目标值在左边索引-中间值
            return binarySearch(arr, left, mid-1, value);
        }else {
            //找到
            return mid;
        }
        
    }
}
​

插值查找

要求：目标数组要是有序数组

方法：与二分查找类似，将mid的计算方法改为mid=left+(right-left)*(value-arr[left])/(arr[right]-arr[left]),理解为查找值在左右索引插值所占比例再乘以做右索引长度

//插值查找
public class InsertValueSearch
{
    public static void main(String[] args)
    {
        int arr[]= {1,2,4,6,9,12,15,44};
        System.out.println(insertValueSearch(arr, 0, arr.length-1, 15));
    }
    
    //arr[]目标值所在数组，value目标值
    //left左边索引，right右边索引
    public static int insertValueSearch(int arr[],int left,int right,int value) {
        //没找到
        //<arr[left]以及>arr[arr.length-1]保证数组不会越界
        //举例：当数组查找值为一个很大的数时，mid根据计算就会很大，但数组长度并没用那么大，所以就会越界，插入很小的数时，mid会计算出负数
        if(left>right ||value<arr[left]||value>arr[arr.length-1]) {
            return -1;
        }
        int mid=left+(right-left)*((value-arr[left])/(arr[right]-arr[left]));
        if(arr[mid]<value) {
            //目标值在中间值-右边索引
            return insertValueSearch(arr, mid+1, right, value);
        }else if(arr[mid]>value){
            //目标值在左边索引-中间值
            return insertValueSearch(arr, left, mid-1, value);
        }else {
            //找到
            return mid;
        }
        
    }
}
​

斐波那契查找

要求：目标数组要为有序数组

• 黄金分割点:将一条线段分为两段f1,f2,使得f1和f之比等于f2和f1之比，分割点叫做黄金分割点

• 斐波那契数列(1,1,2,3,5,8,13)规律为：

• 从第三项开始f(n)=f(n-1)+f(n-1),公式可以变形为f(n)-1=[f(n-1)-1]+[f(n-2)-1]+1

• 将任何一组有序线性表(长度为f(n)-1)可以分为两段f(n-1)-1和f(n-2)-1两段，则中间mid值为left+f(k-1)-1

• 分割出来的每个子段也可以按照这样进行分割

• 线性表的长度不一定等于f(n)-1,则需要将线性表补成长度>=f(n)-1,新增位置的值赋值为数组最后一位即可

//斐波那契查找
import java.util.Arrays;
public class FibonaciSearch
{
    static int maxSize=20;
    public static void main(String[] args)
    {
        int arr[]= {1,2,4,6,9,12,15,44};
        System.out.println(fibonaciSearch(arr, 0, arr.length-1, 4));
    }
    
    //arr[]目标值所在数组，value目标值
    //left左边索引，right右边索引
    public static int fibonaciSearch(int arr[],int left,int right,int value) {
        int k=0;
        if(left>right) {
            return -1;
        }
        //构造斐波那契数列
        int fibonaci[]=new int[maxSize];
        fibonaci[0]=1;
        fibonaci[1]=1;
        for(int i=2;i<arr.length;i++) {
            fibonaci[i]=fibonaci[i-1]+fibonaci[i-2];
        }
        //补全目标数组长度
        while(right>fibonaci[k]-1) {
            k++;
        }
        int temp[]=Arrays.copyOf(arr,fibonaci[k]-1);
        for(int i=arr.length;i<temp.length;i++) {
            temp[i]=temp[arr.length-1];
        }
        while(left<=right) {
            //计算mid值，进行数据查找