【算法】顺序查找、二分查找、插值查找、斐波那契查找 (源码和思路)

Bertha 。 2023-09-23 19:21 93阅读 0赞

### 目录 ###

*  查找算法
 *   *  1.线性(顺序)查找
     *   *  (1)思路
         *  (2)代码实现(java)
     *  2.二分(折半)查找
     *   *  (1)思路
         *  (2)代码实现(java)
     *  3.插值查找
     *   *  (1)思路
         *  (2)代码实现(java)
     *  4.斐波那契(黄金分割法)查找
     *   *  (1)思路
         *  (2)代码实现(java)

# 查找算法 #

## 1.线性(顺序)查找 ##

### (1)思路 ###

> 判断序列中是否包含某个元素，找到提示并输出下标值  
> 初始数组：\{13,4,88,28,6\}，找到88这个值的下标。

### (2)代码实现(java) ###

/**
     * 顺序(线性)查找
     * author：xinxin
     */
    public class SeqSearch {
        
        public static void main(String[] args) {
        
            int[] arr = {
        13,4,88,28,6};
            int result = seqSearch(arr,88);
            System.out.println("下标为:"+result);
        }
    
        /**
         * @param arr  无序序列
         * @param value 需要找的值
         * @return
         */
        public static int seqSearch(int[] arr,int value){
        
            //线性查找，逐一对比，发现相同值，返回下标
            for (int i = 0; i < arr.length ; i++) {
        
                if (arr[i] == value){
        
                    return i; //返回下标
                }
            }
            return -1;
        }
    }

## 2.二分(折半)查找 ##

### (1)思路 ###

> 注意：二分查找的前提是序列是有序的。  
> 初始数组：\{1,2,3,4,5,6,7,8,9\}，查找3这个值，并输出下标，没有就提示

![在这里插入图片描述][46de3e95534d420e9a05c421b4f02a93.gif_pic_center]

### (2)代码实现(java) ###

/**
     * 二分查找
     * author：xinxin
     */
    public class BinarySearch {
        
        public static void main(String[] args) {
        
            int[] arr = {
        1,2,3,4,5,6,7,8,9};
            List<Integer> resValList = binarySearch(arr, 0, arr.length - 1, 3);
            System.out.println("要找的值下标为："+resValList);
        }
    
        /**
         * @param arr    初始数组
         * @param left   左索引
         * @param right  右索引
         * @param value  要找的值
         * @return
         */
        public static List<Integer> binarySearch(int[] arr, int left, int right, int value){
        
            //没找到值
            if (left > right){
        
                return new ArrayList<Integer>();
            }
            int mid = (left + right) / 2;
            int midVal = arr[mid];
            //向右递归
            if (midVal < value){
        
                return binarySearch(arr,mid+1,right,value);
            }else if (midVal > value){
        //向左递归
                return binarySearch(arr,left,mid-1,value);
            }else{
        //正好找到了(包含出现多个相同的值)
                ArrayList<Integer> resValList = new ArrayList<>();
                //向左扫描，看看是否存在相同的值
                int temp = mid - 1;
                while(true){
        
                    if (mid < 0 || arr[temp] != value){
        //退出
                        break;
                    }
                    resValList.add(temp);
                    temp = temp - 1;//左移
                }
    
                //向右扫描，看看是否存在相同的值
                temp = mid + 1;
                while(true){
        
                    if (mid > arr.length-1 || arr[temp] != value){
        //退出
                        break;
                    }
                    resValList.add(temp);
                    temp = temp + 1;//右移
                }
                resValList.add(mid);
                return resValList;
            }
        }
    }

## 3.插值查找 ##

### (1)思路 ###

> 插值查找类似于二分查找，不同的是每次都是mid处查找，对于数据量比较大，分布比较均匀，适合用插值查找。  
> 公式：mid = left + (right - left) \* (value - arr\[left\]) / (arr\[right\] - arr\[left\]) //left代表左索引，right代表右索引，value就是要查找的值  
> 初始数组：\[1,2,3…100\]  
> 找值 1 ， mid = 0 + (99 - 0) \* (1 - 1) / (100 - 1) = 0  
> 找值100，mid= 0 + (99 - 0)\*(100 - 1)/(100 - 1) = 99

### (2)代码实现(java) ###

/**
     * 插值查找
     * author：xinxin
     */
    public class InsertSearch {
        
        public static void main(String[] args) {
        
            int[] arr = new int[100];
            for (int i = 0; i < 100; i++) {
        
                arr[i] = i + 1;
            }
            int index = insertSearch(arr,0,arr.length-1,23);
            System.out.println("下标为："+index);
        }
    
        public static int insertSearch(int[] arr,int left,int right,int value){
        
            //要找的值不存在
            if (left > right || arr[left] < arr[0] || arr[right] > arr[arr.length-1]){
        
                return -1;
            }
            //找mid的公式
            int mid = left + (right - left) * (value - arr[left]) / (arr[right] - arr[left]);
            if (arr[mid] > value){
        //向左递归
                return insertSearch(arr,left,mid-1,value);
            }else if (arr[mid] < value){
        //向右递归
                return insertSearch(arr,mid+1,right,value);
            }else{
        //正好找到
                return mid;
            }
        }
    }

## 4.斐波那契(黄金分割法)查找 ##

### (1)思路 ###

> 黄金分割：一条线段分割成两部分，其中一部分比上全长，接近0.618。  
> 和前面两个相似，仅仅改变了中间结点(mid)，mid位于黄金分割点附近,mid = left + F(k-1)-1, F是斐波那契数列，k代表第几个元素。  
> 斐波那契数列：\{1,1,2,3,5,8,13\} 从第三个元素开始，就是前两个数相加的值。  
> 初始数组：\{1,6,16,26,888,1234\},使用斐波那契查找。

![在这里插入图片描述][8c1db0dd9f8d425faa516215bdcfe851.png]

### (2)代码实现(java) ###

/**
     * 斐波那契查找
     * author：xinxin
     */
    public class FibonacciSearch {
        
        static int  maxSize = 20;
        public static void main(String[] args) {
        
            int[] arr = {
        1,6,16,26,888,1234};
            int resVal = fibonacciSearch(arr,16);
            System.out.println("斐波那契查找下标为："+resVal);
        }
    
        /**
         * 生成一个斐波那契数组
         * @return
         */
        public static int[] fib(){
        
            int[] fib = new int[maxSize];
            fib[0] = 1;
            fib[1] = 1;
            for (int i = 2; i < maxSize; i++) {
        
                fib[i] = fib[i-1] + fib[i-2];
            }
            return fib;
        }
    
        /**
         * @param arr   初始数组
         * @param value 要查找的值
         * @return 返回值，没找到返回 -1，找到返回下标
         */
        public static int fibonacciSearch(int[] arr,int value){
        
            int left = 0;
            int right = arr.length-1;
            int k = 0; //斐波那契数值的下标
            int mid = 0;
            int[] fib = fib();//获取斐波那契数列
            //获取斐波那契分割数值下标
            while(right > fib[k] - 1){
        
                k++;
            }
            int[] temp = Arrays.copyOf(arr,fib[k]);
            for (int i = right + 1; i < temp.length; i++) {
        
                temp[i] = arr[right];
            }
    
            //找到我们要找的值
            while(left <= right){
        
                mid = left + fib[k-1] - 1;
                if (value < temp[mid]){
        //向左查找
                    right = mid - 1;
                    k--;
                }else if (value > temp[mid]){
        //向右查找
                    left = mid + 1;
                    k = k - 2;
                }else {
        //找到
                    if (mid <= right){
        
                        return mid;
                    }else {
        
                        return right;
                    }
                }
            }
            return -1;
        }
    }

[46de3e95534d420e9a05c421b4f02a93.gif_pic_center]: https://img-blog.csdnimg.cn/46de3e95534d420e9a05c421b4f02a93.gif#pic_center
[8c1db0dd9f8d425faa516215bdcfe851.png]: https://img-blog.csdnimg.cn/8c1db0dd9f8d425faa516215bdcfe851.png