二分查找算法(递归与非递归)与插值查找算法

Love The Way You Lie 2023-07-08 09:23 57阅读 0赞

## 二分查找算法 ##

二分查找算法不作过多的文字说明，请看代码和注释  
使用**递归查找**

public class BinarySearch { 
    
        public static void main(String[] args) { 
            int[] array = { 3,4,6,7,12,34,56,78};
            int index = search(array, 0, array.length - 1, 78);
            if (index > 0) { 
                System.out.println("找到要查找的值得下标：" + index);
            }else { 
                System.out.println("没有找到要查找的值");
            }
        }
    
        /** * 二分查找的数组必须是有序，该方法规定算组以升序排序 * @param arry 查找 值 的 目标数组 * @param left 查找开始的左索引 * @param right 查找的右索引 * @param val 查找的目标值 */
        public static int search(int[]  arry, int left, int right, int val) { 
            // 递归退出的条件，说明没有找到要数
            if (left > right) { 
                return -1;
            }
            int mid = (left + right) / 2;
            if (arry[mid] > val) { 
                // 向左递归
                return search(arry, left, mid - 1, val);
            } else if (arry[mid] < val) { 
                // 向右递归
                return search(arry,mid + 1, right, val);
            }else { 
                // arry[mid] = val
                // 代码走到这说明已经找到
                return mid;
            }
        }
    }

使用**非递归**的二分查找

public class BinarySearch { 
        public static void main(String[] args) { 
            int[] arr = { 1,3, 8, 10, 11, 67, 100};
            int search = search(arr, 101);
            System.out.println("找到了，下标：" + search);
        }
    
        /** * 非递归的 二分查找算法 * @param arr * @param targertVal * @return */
        public static int search(int[] arr, int targertVal) { 
            if (arr == null || arr.length == 0) { 
                return -1;
            }
            // 左边索引
            int leftIndex = 0;
            // 右边索引
            int rightIndex = arr.length - 1;
    
            while (leftIndex <= rightIndex) { 
                int midIndex = (leftIndex + rightIndex)/2;
                if (arr[midIndex] == targertVal) { 
                    return midIndex;
                } else if (arr[midIndex] > targertVal) { 
                    rightIndex = midIndex - 1;
                }else { 
                    leftIndex = midIndex + 1;
                }
            }
            // 循环结束，代码走到这，则没有找到
            return -1;
        }
    }

## 插值查找算法 ##

### 插值查找原理介绍： ###

1.  插值查找算法类似于二分查找，不同的是插值查找每次从自适应mid处开始查找。
2.  将折半查找中的求mid 索引的公式 , low 表示左边索引left, high表示右边索引right.key 就是前面我们讲的 findVal  
    ![在这里插入图片描述][20200226090832260.png]
3.  `int mid = low + (high - low) * (key - arr[low]) / (arr[high] - arr[low])` ;/*插值索引*/对应前面的代码公式：`int mid = left + (right – left) * (findVal – arr[left]) / (arr[right] – arr[left])`

### 代码示例 ###

public class BinarySearch { 
    
        public static void main(String[] args) { 
            int[] array = { 3,4,6,7,12,34,56,78};
            int index = insertValueSearch(array, 0, array.length - 1, 78);
            if (index > 0) { 
                System.out.println("找到要查找的值得下标：" + index);
            }else { 
                System.out.println("没有找到要查找的值");
            }
        }
    
        /** * 二分查找的数组必须是有序，该方法规定算组以升序排序 * @param arr 查找 值 的 目标数组 * @param left 查找开始的左索引 * @param right 查找的右索引 * @param findVal 查找的目标值 */
        public static int insertValueSearch(int[]  arr, int left, int right, int findVal) { 
            System.out.println("##########################");
            // 递归退出的条件，说明没有找到要数
            if (left > right || findVal < arr[0] || findVal > arr[arr.length - 1]) { 
                return -1;
            }
            int mid = left + (right - left) * (findVal - arr[left]) / (arr[right] - arr[left]);
            if (arr[mid] > findVal) { 
                // 向左递归
                return insertValueSearch(arr, left, mid - 1, findVal);
            } else if (arr[mid] < findVal) { 
                // 向右递归
                return insertValueSearch(arr,mid + 1, right, findVal);
            }else { 
                // arry[mid] = val
                // 代码走到这说明已经找到
                return mid;
            }
        }
    }

运行结果：

##########################
    找到要查找的值得下标：7

从结果可以看出 ，通过插值查找可以减少查找的次数（即减少递归调用的次数），因而有较高的效率。

**总结**：

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

[20200226090832260.png]: https://img-blog.csdnimg.cn/20200226090832260.png