2023-11-10 16:13:46
介绍
插值查找（Insert Value Search）是二分查找的一种改良，主要是改良了mid的值，mid的值由原来的mid = (left + right) / 2而变成了自适应获取mid的值mid = left + (num - arr[left]) / (arr[right] - arr[left]) * (right - left)，上述公式是前辈们推导出来的，其余和二分查找一样。
对于数据量较大，关键字分布比较均匀的查找表来说，采用插值查找，速度较快。而关键字分布不均匀的情况下，该方法不一定比二分查找要好。
public static int insertValueSearch(int[] arr, int num) { return insertValueSearch(arr, 0, arr.length - 1, num); } public static int insertValueSearch(int[] arr, int left, int right, int num) { //如果没有找到 if (left > right || num < arr[0] || num > arr[arr.length - 1]) { return -1; } //获取中间索引 int mid = left + (num - arr[left]) / (arr[right] - arr[left]) * (right - left); //往左边递归找 if (num < arr[mid]) { return insertValueSearch(arr, left, mid - 1, num); } //往右边递归找 else if (num > arr[mid]) { return insertValueSearch(arr, mid + 1, right, num); } //数据位置找到 else { return mid; } }