8.查找算法

8.查找算法
强烈推介IDEA2020.2破解激活,IntelliJ IDEA 注册码,2020.2 IDEA 激活码

目录

1.查找算法介绍
2.线性查找
3.二分查找
4.插值查找
5.斐波那契查找

1.查找算法介绍

在java中,常用的查找有四种:

(1) 顺序(线性)查找
(2) 二分查找/折半查找
(3) 插值查找
(4) 斐波那契查找

2.线性查找

线性查找非常简单,逐一比对,发现相同的值,则返回下标。

代码实现:

package search;

public class SequenceSearch {
   

    public static void main(String[] args) {
   
        int[] array = {
   1, 9, 11, -1, 34, 89};
        int index = search(array,11);
        System.out.println(index==-1?"没有找到!":"找到!下标为:"+index);
    }

    /** * 线性查找,逐一比对,发现相同的值,则返回下标 * 找到一个满足条件的值就返回 * @param array * @param value * @return */
    public static int search(int[] array, int value){
   
        for (int i = 0; i < array.length; i++) {
   
            if (array[i] == value){
   
                return i;
            }
        }
        return -1;
    }
}

3.二分查找

二分查找介绍:

二分查找也称折半查找(Binary Search),它是一种效率较高的查找方法。但是,折半查找要求线性表必须采用顺序存储结构,而且表中元素按关键字有序排列。

二分查找的思路分析:

  1. 首先确定该数组的中间的下标 mid = (left + right) / 2;
  2. 然后让需要查找的数 findVal 和 arry[mid] 比较:
    2.1 findVal > arry[mid] , 说明你要查找的数在mid 的右边, 因此需要递归向右查找
    2.2 findVal < arry[mid], 说明你要查找的数在mid 的左边, 因此需要递归向左查找
    2.3 findVal == arry[mid] 说明找到,就返回
  3. 结束递归的条件:
    3.1 找到就结束递归 ;
    3.2 递归完整个数组,仍然没有找到findVal ,也需要结束递归 当 left > right 就需要退出。

代码实现:

package search;

/** * 二分查找的前提是数组是有序的,这里以升序为例 */
public class BinarySearch {
   

    public static void main(String[] args) {
   
        int[] array = {
   1, 8, 10, 89, 100, 123};
        System.out.println(search(array,0,array.length-1,100));
    }

    /** * 二分法找到一个数时返回下标 * @param array * @param left * @param right * @param value * @return */
    public static int search(int[] array, int left, int right, int value){
   
        int mid = (left+right)/2;
        int midValue = array[mid];
        if (left>right){
   //没有找到
            return -1;
        }
        if (value > midValue){
   //向右递归
            return search(array,mid+1,right,value);
        } else if (value < midValue){
   //向左递归
            return search(array,left,mid-1,value);
        }else {
   //找到
            return mid;
        }
    }
}

当一个有序数组中有多个相同的待查找值时,需要返回所有下标的解决方案如下:

package search;

import java.util.ArrayList;
import java.util.List;

/** * 二分查找的前提是数组是有序的,这里以升序为例 */
public class BinarySearch {
   

    public static void main(String[] args) {
   
        int[] array = {
   1, 8, 10, 89, 100, 100, 100, 100, 100, 123};
        System.out.println(search(array,0,array.length-1,100));
    }

    /** * 当一个有序数组中,有多个相同的数值时,二分法找到所有下标,返回下标集合 * @param array * @param left * @param right * @param value * @return */
    public static List<Integer> search(int[] array, int left, int right, int value){
   
        int mid = (left+right)/2;
        int midValue = array[mid];
        if (left>right){
   //没有找到返回空集合
            return new ArrayList();
        }
        if (value > midValue){
   //向右递归
            return search(array,mid+1,right,value);
        } else if (value < midValue){
   //向左递归
            return search(array,left,mid-1,value);
        }else {
   //找到
            //由于二分查找的前提是数组有序,所以找到后的多个值一定在一起,从mid开始向左右搜索相同的值的下标都放入集合
            List<Integer> valueIndexs = new ArrayList<>();
            int i = mid-1, j = mid+1;
            boolean isEnd = false;
            while (!isEnd){
   
                isEnd = true;
                if (array[i]==midValue){
   
                    valueIndexs.add(i--);
                    isEnd = false;
                }
                if (array[j]==midValue){
   
                    valueIndexs.add(j++);
                    isEnd = false;
                }
            }
            valueIndexs.add(mid);
            return valueIndexs;
        }
    }
}

4.插值查找

差值查找介绍:

在上述使用二分查找算法时,会发现有个问题,例如在1~100的一个有序序列中查找1,即在均匀分布的序列中,二分查找需要多次递归折半后才能定位到要查找的数。那有没有一种更快定位的方法呢?于是插值查找是对二分查找的一种优化,每次从自适应mid处开始查找,而不是从固定的中间mid出查找。

插值查找原理:

插值查找算法类似于二分查找,不同的是插值查找每次从自适应mid处开始查找。修改折半查找中的求mid 索引的公式:在这里插入图片描述在这里插入图片描述

代码实现:

package search;

public class InsertValueSearch {
   

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

    public static int search(int[] array, int left, int right, int value){
   
        if (left>right || value<array[left] || value>array[right]){
   
            return -1;
        }
        //求出自适应mid
        int mid = left + (right-left) * (value-array[left])/(array[right]-array[left]);
        int midValue = array[mid];
        if (midValue < value){
   //向右递归
            return search(array,mid+1,right,value);
        }else if (midValue > value){
   //向左递归
            return search(array, left, mid-1,value);
        }else {
   //找到
            return mid;
        }
    }
}

插值查找注意事项:

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

5.斐波那契查找

斐波那契查找介绍:

斐波那契查找,是二分查找的一个变种。其时间复杂度 O(log2n) 。斐波那契数列又称黄金分割数列。

黄金分割点是指把一条线段分割为两部分,使其中一部分与全长之比等于另一部分与这部分之比。取其前三位数字的近似值是0.618。由于按此比例设计的造型十分美丽,因此称为黄金分割,也称为中外比。这是一个神奇的数字,会带来意向不大的效果。

斐波那契数列 {1, 1, 2, 3, 5, 8, 13, 21, 34, 55 } 发现斐波那契数列的两个相邻数的比例,无限接近黄金分割值0.618,且从第三个元素开始,其值等于前两个元素的和。

斐波那契(黄金分割法)原理:

斐波那契查找原理同样与二分查找相似,仅仅改变了中间结点(mid)的位置,mid不再是中间或插值得到,而是根据斐波那契数列进行分割。

分割方法:

在斐波那契数列中找一个大于等于查找表中元素总数的数F[k](F代表斐波那契数列),将原查找表长度扩展为F[k](如果元素总数小于F[k]则补充元素,补充重复最后一个元素,直到满足F[k]个元素),然后进行斐波那契分割,即将F[k]个元素分割为前半部分F[k-1]个元素,后半部分F[k-2]个元素。例如将10个元素的查找表扩容到13个元素,然后分割成左边长度为8的子序列和右边长度为5的子序列。
 
所以由上面的推理可得,mid分割点的位置为:mid=left+F(k-1),即查找表第一个元素下标加上左子查找表的长度,这样递归左子查找表的范围为left~mid-1,右子查找表的范围为mid~right。这种方法是我自己推出的比较好理解的解决方法,可以发现如果走的右子查找表,已经比较了的mid位置的数会再次放到右子查找表中,但我简单推了一下后基本不影响效率。
 
另一种比较正统的理解是:由斐波那契数列 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)-1F(k-2)-1左右两部分,其中mid=low+F(k-1)-1
在这里插入图片描述
示例代码采用该流程实现,用我的那种思路只需要稍微调整:
在这里插入图片描述

代码实现:

package search;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class FibonacciSearch {
   

    public static int maxSize = 20;
    public static void main(String[] args) {
   
        int [] arr = {
   1,8, 10, 89, 100, 123};

        System.out.println("index=" + fibSearch(arr, 123));

    }

    /** * 根据数组长度构建一个合适的斐波那契数列 * @return */
    public static Integer[] fib(int arrayLength) {
   
        List<Integer> fibList = new ArrayList<>();
        fibList.add(1);
        fibList.add(1);
        //斐波那契数列从第三个数开始等于前两个数的和
        for (int i = 1; fibList.get(i) < arrayLength; i++) {
   
            fibList.add(fibList.get(i)+fibList.get(i-1));
        }
        Integer[] fibArray = new Integer[fibList.size()];
        System.out.println("构建的斐波那契数列:"+fibList);
        fibList.toArray(fibArray);
        return fibArray;
    }

    /** * 斐波那契非递归查找 * @param array 数组 * @param value 我们需要查找的值 * @return 返回对应的下标,如果没有-1 */
    public static int fibSearch(int[] array, int value) {
   
        int left = 0;
        int right = array.length - 1;
        int k = 0; //表示斐波那契数列中数值的下标
        int mid = 0; //存放mid值
        Integer[] fib = fib(array.length); //获取到斐波那契数列
        //获取斐波那契数列中查找表应该扩容到的长度数值的下标
        k = fib.length-1;
        //扩容数组
        int[] tempArray = new int[fib[k]-1];
        for(int i = 0; i < tempArray.length; i++) {
   
            if (i>right){
   
                tempArray[i] = array[right];
            }else {
   
                tempArray[i] = array[i];
            }
        }
        System.out.println("扩容后的查找表:"+Arrays.toString(tempArray));
        // 使用while循环的非递归方式处理,避免反复创建斐波拉契数列
        while (left <= right) {
   
            mid = left + fib[k-1] - 1;
            if(value < tempArray[mid]) {
    //向左子查找表继续查找
                right = mid - 1;
                k--;
            } else if (value > tempArray[mid]) {
    //向右子查找表继续查找
                left = mid + 1;
                k -= 2;
            } else {
    //找到
                //需要确定,返回的是哪个下标
                if(mid <= right) {
   
                    return mid;
                } else {
   
                    return right;
                }
            }
        }
        return -1;
    }
}

优劣势分析:

mid左侧的元素个数大于右侧的元素个数。所以,如果要查找的记录在右侧,则左侧的数据就不需要比较了,效率比较高;如果要查找的记录在左侧,则效率比较低。

本文来源MrKorbin,由架构君转载发布,观点不代表Java架构师必看的立场,转载请标明来源出处:https://javajgs.com/archives/25278

发表评论