投稿
  1. 极客之音首页
  2. 后端开发
  3. Java

Java数据结构之二分查找/插值查找/斐波那契查找

小半 • • Java • 阅读 81

导读：本篇文章讲解 Java数据结构之二分查找/插值查找/斐波那契查找，希望对大家有帮助，欢迎收藏，转发！站点地址：www.bmabk.com

目录

一.简单的线性查找

1.问题引出

2.代码实现

二.二分查找算法

1.基本介绍

2.代码实现(递归)

3.代码实现(非递归)

4.二分查找的功能完善

三.插值查找

1.简单介绍

2.代码实现(递归)

4.注意事项

四.斐波那契查找

1.基本介绍

2.代码实现(非递归)

一.简单的线性查找

1.问题引出

有一个数列:{1, 9, 45, 5, 69, 13, 58}，判断数列中是否包含此数

【顺序查找】要求:如果找到了，就提示找到，并给出下标值

2.代码实现

public class SeqSearch {
    public static void main(String[] args) {
        int[] arr = {1, 9, 45, 5, 69, 13, 58};
        int i = seqSearch(arr, 5);
        if (i == -1)
            System.out.println("未查找到");
        else
            System.out.println("下标为:" + i);


    }

    //线性查找
    public static int seqSearch(int[] arr, int value) {
        //线性查找是逐一比对,发现有相同值,就返回下标
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == value)
                return i;


        }
        return -1;

    }
}

几种结果

System.out.println(seqSearch(arr, 5));        ---------3
System.out.println(seqSearch(arr, 1));        ---------0         System.out.println(seqSearch(arr, 0));        ---------1

二.二分查找算法

1.基本介绍

二分查找:
请对一个有序数组进行二分查找{1,8，10，89，1000，1234}，输入一个数看看该数组是否存在此数，并且求出下标，如果没有就提示”没有这个数”。

二分查找的思路分析
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 class BinarySearch {
    public static void main(String[] args) {
        int[] arr = {1, 8, 10, 89, 1000, 1000,1234};
        System.out.println(binarySearch(arr, 0, arr.length - 1, 1000));

    }

    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 mid;
        else if (arr[mid] > value) {
            //向左递归
            return binarySearch(arr, left, mid - 1, value);
        } else {
            //向右递归
            return binarySearch(arr, mid + 1, right, value);
        }


    }
}

几种结果

System.out.println(binarySearch3(arr,0,arr.length-1,1234));  ------6
System.out.println(binarySearch3(arr,0,arr.length-1,1));     ------1
System.out.println(binarySearch3(arr,0,arr.length-1,567));  ------(-1)

3.代码实现(非递归)

  public static int binarySearch3(int[] arr, int value) {
        int left = 0;
        int right = arr.length - 1;
        int mid;
        while (left <= right) {
            mid = (left + right) / 2;
            if (arr[mid] > value) {//向左找
                right = mid - 1;
            } else if (arr[mid] < value) {//向右找
                left = mid + 1;
            } else {
                return mid;
            }

        }
        return -1;


    }

几种结果

System.out.println(binarySearch3(arr,1234));  ------6
System.out.println(binarySearch3(arr,1));     ------1
System.out.println(binarySearch3(arr,567));  ------(-1)

4.二分查找的功能完善

问题引出:{1,8，10，89，1000，1000，1234}当一个有序数组中，有多个相同的数值时,如何将所有的数值都查找到，比如这里的1000,应该返回4,5

代码实现(递归)

//二分查找的数组必须是有序的
public class BinarySearch {
    public static void main(String[] args) {
        int[] arr = {1, 8, 10, 89, 1000, 1000,1234};
        System.out.println(binarySearch2(arr, 0, arr.length - 1, 100));

    }

   
    public static List<Integer> binarySearch2(int[] arr, int left, int right, int value) {
        List<Integer> list = new ArrayList<>();
        if (left > right){
            list.add(-1);
            return list;
        }

        int mid = (left + right) / 2;
        if (arr[mid] == value){
            list = new ArrayList<>();
            list.add(mid);
            int temp=mid-1;
            while(temp>=0&&value==arr[temp]){
                list.add(temp);
                temp--;
            }
            temp=mid+1;
            while(temp<arr.length&&value==arr[temp]){
                list.add(temp);
                temp++;
            }
            return list;
        }

        else if (arr[mid] > value) {
            //向左递归
            return binarySearch2(arr, left, mid - 1, value);
        } else {
            //向右递归
            return binarySearch2(arr, mid + 1, right, value);
        }


    }
}

几种结果

System.out.println(binarySearch2(arr, 0, arr.length - 1, 100));  ----(-1)
System.out.println(binarySearch2(arr, 0, arr.length - 1, 1000));   ----[5, 4]

三.插值查找

1.简单介绍

折半查找的缺点:

当我们查找1–100的数中的1的时候,显然mid=50,一直折半查找步骤很多,我们是否可以找到一个合适的值来作为mid减少折半的次数呢?

1)插值查找算法类似于二分查找，不同的是插值查找每次从自适应mid处开始查找。
2）将折半查找中的求mid索引的公式, low表示左边索引, high表示右边索引.

Java数据结构之二分查找/插值查找/斐波那契查找

3) int midlIndex = low +(high – low)* (key – arr[low])/ (arr[high] – arr[low])

2.代码实现(递归)

public class InsertSort {
    public static void main(String[] args) {
        int[] arr=new int[100];
        for(int i=0;i<100;i++){
            arr[i]=i+1;
        }
        System.out.println(insertValueSearch(arr, 0, arr.length - 1, 1));

    }
    //编写插值查找算法
    public static int insertValueSearch(int[] arr,int left,int right,int value){

        if(right<left)
            return -1;
        int mid=left+(right-left)*(value-arr[left])/(arr[right]-arr[left]);
        if(arr[mid]>value){
            return insertValueSearch(arr,left,mid-1,value);
        }
        else if(arr[mid]<value){
            return insertValueSearch(arr,mid+1,right,value);
        }
        else {
            return mid;
        }




    }
}

几种结果

System.out.println(insertValueSearch(arr, 0, arr.length - 1, 1));  ----0

System.out.println(insertValueSearch(arr, 0, arr.length - 1, 5)); -----4

System.out.println(insertValueSearch(arr, 0, arr.length - 1, 101)); -----(-1)

3.代码实现(非递归)

 public static int insertValueSearch2(int[] arr,int value){
        int left = 0;
        int right = arr.length - 1;
        int mid;
        while (left <= right) {
            mid = left+(right-left)*(arr[right]-value)/(arr[right]-arr[left]);
            if (arr[mid] > value) {//向左找
                right = mid - 1;
            } else if (arr[mid] < value) {//向右找
                left = mid + 1;
            } else {
                return mid;
            }

        }
        return -1;
    }

几种结果

System.out.println(insertValueSearch(arr,1));  ----0

System.out.println(insertValueSearch(arr,5)); -----4

System.out.println(insertValueSearch(arr,101)); -----(-1)

4.注意事项

1)对于数据量较大，关键字分布比较均匀的查找表来说，采用插值查找,速度较快.
2)关键字分布不均匀的情况下，该方法不一定比折半查找要好

四.斐波那契查找

1.基本介绍

斐波那契数列{1,2,3,5,8,13,21,34,55}发现斐波那契数列的两个相邻数的比例，无限接近黄金分割值0.618

原理

斐波那契查找原理与前两种相似，仅仅改变了中间结点(mid）的位置，mid不再是中间或插值得到，而是位于黄金分割点附近，即mid=low+F(k-1)-1(F代表斐波那契数列），如下图所示

Java数据结构之二分查找/插值查找/斐波那契查找

 

对F(k-1)-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

2)类似的，每一子段也可以用相同的方式分割

3)但顺序表长度n不一定刚好等于F[K]-1，所以需要将原来的顺序表长度n增加至F[K]-1。这里的k值

只要能使得F[k]-1恰好大于或等于n郎可，由以下代码得到,顺序表长度增加后，新增的位置（从n+1到FIk]-1位置），都赋为n位置的值即可。

while(n>fib(k)-1)
k++;

2.代码实现(非递归)

public class FibonacciSearch {

    public static int maxSize=20;

    public static void main(String[] args) {
        int[] arr={1,8,10,89,1000,1234};
        System.out.println("查找的index为:"+fibonacciSearch(arr, 12134));
    }
    //因为后面我们mid=low+F(k-1)-1,需要使用到斐波那契数列,因此我们需要先获取到一个斐波那契数列
    public static int[] fibonacci(){
       int[] f= new int[maxSize];
       f[0]=1;
       f[1]=1;
       for(int i=2;i<maxSize;i++){
           f[i]=f[i-1]+f[i-2];
       }
       return f;

    }
    public static int fibonacciSearch(int[] arr,int key){
        int low=0;
        int high=arr.length-1;
        int mid;
        int f[]=fibonacci();
        int k=0;  //表示斐波那契数组的下标
        //获取到斐波那契额数列分割数值的下标
        while (high>f[k]-1){
            k++;
        }
        //因为f[k]的值可能大于arr数组的长度,所以我们需要构造一个长度为f[k]的数组,不足的部分用0补齐
        int[] temp = Arrays.copyOf(arr, f[k]);
        //实际上需求使用a数组最后的数填充temp
        for(int i=arr.length;i<temp.length;i++){
            temp[i]=arr[arr.length-1];
        }

        //使用while循环处理,找到key
        while(low<=high){
            mid=low+f[k-1]-1;
            if(key<temp[mid]){//向左查找
              high=mid-1;
              //通过斐波那契额数组将temp分为两部分,前边部分的长度为f[k-1]-1;
              //现在需要对前半部分继续查找,因此k--;
              k--;
            }
            else if(key>temp[mid]){//向右查找
                low=mid+1;
                //通过斐波那契额数组将temp分为两部分,前边部分的长度为f[k-2]-1;
                //现在需要对后半部分继续查找,因此k-=2;
                k-=2;
            }
            else {//找到了
                if(mid<arr.length-1)
                    return mid;
                else
                    return arr.length-1;
            }

        }
        return -1;



    }
}

几种结果

System.out.println("查找的index为:"+fibonacciSearch(arr, 12134)); ----(-1)
System.out.println("查找的index为:"+fibonacciSearch(arr, 1000));  ----4

版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。

文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/101079.html

赞 (0)
小半的头像小半
0 0

相关推荐

极客之音——专业性很强的中文编程技术网站，欢迎收藏到浏览器，订阅我们！