算法与数据结构-06-插值查询
2023-03-20 14:48:07 时间
插值查询
二分查找虽然快捷,但是每次折半查找,查找过程不具有动态性,究其原因是由于待查找元素每次与mid中间值进行比较,但中间值的获取算法是固定的,即(left+right)/ 2 ,如果获取中间值得算法是动态的或许会更高效,这就是插值查询。
package day05; import java.util.Arrays; /** * 二分查找进阶【插值查找】 * 插值寻找公式:int mid=left+(right-left)*(findVal-arr[left])/(arr[right]-arr[left]) */ public class InterpolationSearch { private static int binarySearchNumber = 0; private static int interpolationSearchNumber = 0; public static void main(String[] args) { int[] array = new int[100]; for (int i = 0; i < array.length; i++) { array[i] = i; } // System.out.println(Arrays.toString(array)); // 测试二分查找 查找99需要递归多少次 int binarySearchIndex = binarySearch(99, 0, array.length-1, array); System.out.println(binarySearchIndex); System.out.println("--------------------------------------------"); // 测试插值查找 查找99需要递归多少次 int interpolationSearchIndex = interpolationSearch(99, 0, array.length-1, array); System.out.println(interpolationSearchIndex); } /** * 插值查找 * 使用条件:数组数据有序,数据相对连续 * * @param findVal * @param left * @param right * @param arr * @return */ public static int interpolationSearch(int findVal, int left, int right, int[] arr) { System.out.println("插值查询 查找" + findVal + "递归" + (++interpolationSearchNumber) + "次~"); if (left > right || findVal < arr[left] || findVal > arr[right]) { return -1; } int mid = left + (right - left) * ((findVal - arr[left]) / (arr[right] - arr[left])); int midVal = arr[mid]; if (findVal < midVal) { right = mid - 1; return interpolationSearch(findVal, left, right, arr); } else if (findVal > midVal) { left = mid + 1; return interpolationSearch(findVal, left, right, arr); } else { return mid; } } /** * 二分查找 * 适应条件:数组有序 * * @param findVal * @param left * @param right * @param arr * @return */ public static int binarySearch(int findVal, int left, int right, int[] arr) { System.out.println("二分查询 查找" + findVal + "递归" + (++binarySearchNumber) + "次~"); if (left > right || findVal < arr[left] || findVal > arr[right]) { return -1; } // int mid = left + (1/2)*(right - left) ; int mid = left + (right - left) / 2; // int mid = (left+right)/2; int midVal = arr[mid]; if (findVal < midVal) { right = mid - 1; return binarySearch(findVal, left, right, arr); } else if (findVal > midVal) { left = mid + 1; return binarySearch(findVal, left, right, arr); } else { return mid; } } }结论:经过对比 查询99 二分法需要六次递归,而插值查询只需要一次。 但是插值查询的效率不一定比二分查找效率高。如果数组元素跳跃性大,不够连续,会出现插值查询效率比二分查找效率低的情况发生。
注意:插值查询和二分查找最大的区别就是获取"中间值"的算法不同!!!
相关文章
- Erlang入门(三)——分布式编程
- Erlang入门(四)——错误处理和鲁棒性
- 机器人系统设计与制作:Python语言实现2.4 用LibreCAD生成机器人的二维CAD图
- sicp习题2.33-2.39尝试解答
- odoo 常用widget
- BAT三巨头激辩AI:李彦宏称强人工智能不会到来;马云说So TM What
- Linux性能优化1.1 常用建议
- Linux性能优化1.2 性能调查概要
- Linux性能优化1.3 本章小结
- Linux性能优化2.1 CPU性能统计信息
- Linux性能优化2.2 Linux性能工具:CPU
- Linux性能优化2.3 本章小结
- Linux性能优化3.1 内存性能统计信息
- Linux性能优化3.2 Linux性能工具:CPU与内存
- 想要成为真正优秀的程序员是不是真的很难?
- 2015中国程序员生存报告 你苦你先看
- 2015年年中IT人才市场行情回顾
- 14个专门面向女性开发人员的编程社区
- 即使是封闭的苹果,也不得不开源了
- 如何在编程生涯中有一个好的开端