- 插值查找原理介绍: 插值查找算法类似于二分查找,不同的是插值查找每次从自适应mid 处开始查找。
- 将折半查找中的求mid 索引的公式 , low 表示左边索引 left, high 表示右边索引 right. key 就是前面我们讲的 findVal
- int mid = low + (high - low) * (key - arr[low]) / (arr[high] - arr[low]) ;/插值索引/ 对应前面的代码公式: int mid = left + (right – left) * (findVal – arr[left]) / (arr[right] – arr[left]) 4) 举例说明插值查找算法 1-100 的数组
代码演示
package com.iflytek.search;public class InsertValueSearch { public static void main(String[] args) { int[] arr = {1, 8, 10, 1000, 1111, 1234}; int index = insertValueSearch(arr, 0, arr.length-1, 1000); System.out.println("index = " + index); } public static int insertValueSearch(int[] arr, int left, int right, int findValue) { if (left > right || arr[0] > findValue || arr[arr.length-1] < findValue) { return -1; } int mid = left + (right - left) * (findValue - arr[left]) / (arr[right] - arr[left]); if (findValue > arr[mid]) { return insertValueSearch(arr, mid + 1, right, findValue); } else if (findValue < arr[mid]) { return insertValueSearch(arr, left, mid - 1, findValue); } else { return mid; } }}
插值查找注意事项:
- 对于数据量较大,关键字分布比较均匀的查找表来说,采用插值查找, 速度较快.
- 关键字分布不均匀的情况下,该方法不一定比折半查找要好