[数据结构与算法] 查找算法

分手后的思念是犯贱 2023-07-03 12:24 22阅读 0赞

### 查找算法 ###

*  线性查找
 *  二分查找
 *  差值查找
 *  斐波那契查找

>  鉴于在排序算法时, 搞得比较乱的情况, 导致查找不太方便.  
> 因此, 在写查找算法时, 我会将所有的东西都写在一起, 便于查找和阅读

**在java中，我们常用的查找有四种:**

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

# 线性查找 #

*  **思路:** 如果在数组中发现满足条件的值, 就返回其下标

/** * 线性查找 * @author TimePause * @create 2020-02-06 20:41 */
    public class SeqSearch { 
        public static void main(String[] args) { 
            int arr[] = { 1, 9, 11, -1, 34, 89};
            int index = seqSearch(arr, 89);
            if (index==-1){ 
                System.out.println("未找到相关元素下标");
            }else { 
                System.out.println("该元素的下标为"+index);
            }
    
    
        }
    
        /** * 线性查找 * 发现满足条件的值,返回其下标 * * @param arr * @param keyval * @return */
        public static int seqSearch(int[] arr, int keyval){ 
            for (int i=0;i<arr.length;i++){ 
                if (arr[i]==keyval){ 
                    return i;
                }
            }
            return -1;
        }
    }

# 二分查找 #

**二分查找问题引入：**

*  请对一个有序数组进行二分查找 \{1,8, 10, 89, 1000, 1234\} ，输入一个数看看该数组是否存在此数，并且求出下标，如果没有就提示"没有这个数"。
 *  思考题： \{1,8, 10, 89, 1000, 1000，1234\} 当一个**有序数组**中，有多个相同的数值时，如何将所有的数值都查找到，比如这里的 1000.

**我们根据思路图来理解二分查找**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMzcxNTU2_size_16_color_FFFFFF_t_70]  
**我们根据代码来实现这个算法**

/** * 二分查找法 * * @author TimePause * @create 2020-02-07 15:42 */
    public class BinarySearch { 
        public static void main(String[] args) { 
    
            //测试二分查找
          /* int[] arr = {1, 8, 10, 89, 1000, 1234}; int resIndex = binarySearch(arr, 0, arr.length - 1, 81); System.out.println("resIndex="+resIndex);*/
    
           //测试二分查找改良
            int[] arr = { 1,1,1, 8, 10, 89, 1000, 1234};
            List<Integer> resIndexList = binarySearch2(arr, 0, arr.length - 1, 1);
            System.out.println("resIndexList="+resIndexList.toString());
        }
    
        /** * 二分查找(数据必须有序) * * @param arr 数组 * @param left 左边的索引 * @param right 右边的索引 * @param findVal 要查找的值 * @return 如果找到则返回下标.如果找不到则返回-1 */
        public static int binarySearch(int arr[],int left,int right,int findVal){ 
            // 如果已经遍历结束,但是仍未发现要查找的值,则返回-1
            if (left>right){ 
                return -1;
            }
    		
    		// 设置中间值域中间值的下标
            int mid = (left + right) / 2;
            int midVal = arr[mid];
    
            if (findVal>midVal){ //如果在中间值的右边
                return  binarySearch(arr,mid + 1, right, findVal);
            }else if(findVal<midVal){ //如果在中间值的左边
                return  binarySearch(arr, left, mid - 1, findVal);
            }else { 
                return mid;//如果找到了,则返回该元素所在下标
            }
        }
    
    
        /** * 二分查找法改良,查找多个重复的元素 * 思路分析: * 1.在找到mid的索引值, 不要马上返回 * 2.向mid索引的左边扫描,将满足1000的元素的下标,加入到数组中 * 3.向mid索引的右边扫描,将满足1000的元素的下标,加入到数组中 * 4.将查找到的mid值放入数组后将这个数组返回 * * @param arr * @param left 最左边元素下标 * @param right 最右边元素下标 * @param findVal 要查找的值 * @return */
        public static List<Integer> binarySearch2(int arr[], int left, int right, int findVal){ 
            // 如果已经遍历结束,但是仍为发现要查找的值,则返回一个空的数组, 
            // 我们可以根据返回的数组长度来判断是否查找到元素
            if (left>right){ 
                return new ArrayList<Integer>();
            }
    
    
            // 定义中间值的下标和中间值
            int mid = (left + right) / 2;
            int midVal = arr[mid];
    
            if (findVal>midVal){ //如果在中间值的右边
                return  binarySearch2(arr,mid + 1, right, findVal);
            }else if(findVal<midVal){ //如果在中间值的左边
                return  binarySearch2(arr, left, mid - 1, findVal);
            }else { 
                // 初始化一个数组,用于存放查找到的指定元素的下标
                List<Integer> resIndexList = new ArrayList<Integer>();
                // 向mid的索引值左边扫描, 将所有满足1000的元素的下标, 加入到集合ArrayList
                int temp = mid-1;
                while (true){ 
                    if (temp<0 || arr[temp]!=findVal){ 
                        break;
                    }
                // 否则就将存放下标的temp放入到集合中
                resIndexList.add(temp);
                temp -= 1;
                }
    
                // 将中间的值放入数组
                resIndexList.add(mid);
    
                // 向mid的索引值右边扫描, 将所有满足1000的元素的下标, 加入到集合ArrayList
                temp = mid+1;
                while (true){ 
                    if (temp>arr.length-1 || arr[temp]!=findVal){ 
                        break;
                    }
                // 否则就将存放下标的temp放入到集合中
                resIndexList.add(temp);
                temp += 1;
                }
                return resIndexList;
            }
    
        }
    }

# 差值查找 #

*  **插值查找算法类似于二分查找，不同的是插值查找每次从自适应mid处开始查找。**
 *  将折半查找中的求mid 索引的公式 , low 表示左边索引left, high表示右边索引right.key 就是前面我们讲的 findVal
    
        int mid = low + (high - low) * (key - arr[low]) / (arr[high] - arr[low])  ;/*插值索引*/

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

*  对应前面的代码公式：`int mid = left + (right – left) * (findVal – arr[left]) / (arr[right] – arr[left])`
 *  举例说明插值查找算法 1-100 的数组  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMzcxNTU2_size_16_color_FFFFFF_t_70 1]

**代码实现**

**
     * 插值查找
     *
     * @author TimePause
     * @create 2020-02-08 11:01
     */
    public class InsertValueSearch { 
        public static void main(String[] args){ 
            // 生成1,2,3...100, 一百个数并放入数组
            int[] arr = new int[100];
            for (int i=0;i<100;i++){ 
                arr[i] = i+1;
            }
            // 调用插值查找
            int index = insertVal(arr, 0, arr.length - 1, 1);
            System.out.println("要查找的数组下标为"+index);
        }
    
        /** * 插值查找法,也要要求数组是有序(私以为插值就是二分查找的改良) * * @param arr 数组 * @param left 数组最左下标索引 * @param right 数组最右下标索引 * @param findVal 查找值 * @return 如果找到返回对应元素下标,如果找不到则返回-1 */
        public static int insertVal(int[] arr,int left,int right,int findVal){ 
            System.out.println("要排序1次");//插值排序只会调用一次,因为使用了自适应的mid算法
            // 查找未果的所有情况
            //注意: findVal<arr[0] || findVal >arr.length-1 必须需要
            if (left>right || findVal<arr[0]  || findVal >arr.length-1){ //小于最小值,大于最大值提前退出
                return -1;
            }
            // 插值查找时的mid公式(区分二分查找)
            int mid = left + (right - left) * (findVal - arr[left]) / (arr[right] - arr[left]);
            int midVal = arr[mid];//中间值
            while (true){ 
                if (findVal<midVal){ //要找的值位于左边
                    return insertVal(arr, left, mid - 1, findVal);
                }   else if(findVal>midVal){ //要找的值位于右边
                    return  insertVal(arr, mid + 1, right, findVal);
                }else { 
                    return mid;
                }
            }
    
    
        }
    
    }

**插值查找注意事项：**

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

# 斐波那契查找 #

**斐波那契(黄金分割法)查找基本介绍:**

*  **黄金分割点是指把一条线段分割为两部分，使其中一部分与全长之比等于另一部分与这部分之比**。  
    取其前三位数字的近似值是0.618。由于按此比例设计的造型十分美丽，因此称为黄金分割，也称为中外比。这是一个神奇的数字，会带来意向不大的效果。
 *  **斐波那契数列 \{1, 1, 2, 3, 5, 8, 13, 21, 34, 55 \} 发现斐波那契数列的两个相邻数 的比例，无限接近 黄金分割值0.618**

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

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

**对F(k-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  
    ![在这里插入图片描述][20200208225113320.png]  
    **类似的，每一子段也可以用相同的方式分割**  
    但顺序表长度n不一定刚好等于F\[k\]-1，所以需要将原来的顺序表长度n增加至F\[k\]-1。这里的k值只要能使得F\[k\]-1恰好大于或等于n即可，由以下代码得到,顺序表长度增加后，新增的位置（从n+1到F\[k\]-1位置），都赋为n位置的值即可。

**斐波那契查找应用案例：**  
请对一个有序数组进行斐波那契查找 \{1,8, 10, 89, 1000, 1234\} ，输入一个数看看该数组是否存在此数，并且求出下标，如果没有就提示"没有这个数

**代码实现**

/** * 斐波那契查找 * * @author TimePause * @create 2020-02-08 21:11 */
    public class FibonacciSearch { 
        public static int maxSize = 20;
        public static void main(String[] args){ 
            int[] arr = { 1, 8, 10, 89, 1000, 1234};
            int index = fibSearch(arr, 8);
            System.out.println("index="+fibSearch(arr,89));//0
        }
    
        // 因为后面我们mid=low+F(k-1)-1, 需要使用到斐波那契数列, 因此我们需要获取一个斐波那契数列
        // 创建一个斐波那契数列
        public static int[] fib(){ 
            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;
        }
    
        /** * 编写斐波那契查找方法(使用非递归方式编写算法) * * @param a 数组 * @param key 需要查找的关键码 * @return 返回对应下标,如果没有-1 */
        public static int fibSearch(int[] a,int key){ 
            int low = 0;
            int high = a.length - 1;
            int k = 0; //表示斐波那契分割数值的下标
            int mid = 0; //存放mid值
            int f[] = fib(); //获取到斐波那契数列
            //获取到斐波那契分割数值的下标
            while(high > f[k] - 1) { 
                k++;
            }
            //因为 f[k] 值 可能大于 a 的 长度，因此我们需要使用Arrays类，构造一个新的数组，并指向temp[]
            //不足的部分会使用0填充
            int[] temp = Arrays.copyOf(a, f[k]);
            //实际上需求使用a数组最后的数填充 temp
            //举例:
            //temp = {1,8, 10, 89, 1000, 1234, 0, 0} => {1,8, 10, 89, 1000, 1234, 1234, 1234,}
            for(int i = high + 1; i < temp.length; i++) { 
                temp[i] = a[high];
            }
    
            // 使用while来循环处理，找到我们的数 key
            while (low <= high) {  // 只要这个条件满足，就可以找
                mid = low + f[k - 1] - 1;
                if(key < temp[mid]) {  //我们应该继续向数组的前面查找(左边)
                    high = mid - 1;
                    //为甚是 k--
                    //说明
                    //1. 全部元素 = 前面的元素 + 后边元素
                    //2. f[k] = f[k-1] + f[k-2]
                    //因为 前面有 f[k-1]个元素,所以可以继续拆分 f[k-1] = f[k-2] + f[k-3]
                    //即 在 f[k-1] 的前面继续查找 k--
                    //即下次循环 mid = f[k-1-1]-1
                    k--;
                } else if ( key > temp[mid]) {  // 我们应该继续向数组的后面查找(右边)
                    low = mid + 1;
                    //为什么是k -=2
                    //说明
                    //1. 全部元素 = 前面的元素 + 后边元素
                    //2. f[k] = f[k-1] + f[k-2]
                    //3. 因为后面我们有f[k-2] 所以可以继续拆分 f[k-1] = f[k-3] + f[k-4]
                    //4. 即在f[k-2] 的前面进行查找 k -=2
                    //5. 即下次循环 mid = f[k - 1 - 2] - 1
                    k -= 2;
                } else {  //找到
                    //需要确定，返回的是哪个下标
                    if(mid <= high) { 
                        return mid;
                    } else { 
                        return high;
                    }
                }
            }
            return -1;
    
        }
    
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMzcxNTU2_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200207182339628.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMzcxNTU2,size_16,color_FFFFFF,t_70
[20200208113158687.png]: https://img-blog.csdnimg.cn/20200208113158687.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMzcxNTU2_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200208113458679.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMzcxNTU2,size_16,color_FFFFFF,t_70
[20200208225113320.png]: https://img-blog.csdnimg.cn/20200208225113320.png