type
status
date
slug
summary
tags
category
icon
password
1、插值查找原理介绍
- 插值查找算法类似于二分查找,不同的是插值查找每次从自适应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])
- 举例说明插值查找算法 1-100 的数组
3、代码实现
package com.qf.search; public class InsertValueSearch { public static void main(String[] args) { int[] arr={1,8, 10, 89, 1000, 1234}; int i = insertSearch(arr, 0, arr.length - 1, 1234); System.out.println("查找到的下标为:"+i); } public static int insertSearch(int[] arr,int left,int right,int findValue){ /*int mid = left + (right – left) * (findVal – arr[left]) / (arr[right] – arr[left])*/ System.out.println("hello~"); if (left>right||findValue<arr[left]||findValue>arr[right]){ return -1; } int mid=left + (right-left)*(findValue-arr[left])/(arr[right]-arr[left]); int midValue=arr[mid]; if (midValue<findValue){ //向右查找 return insertSearch(arr,mid+1,right,findValue); }else if (midValue>findValue){ //向左查找 return insertSearch(arr,left,mid-1,findValue); }else{ return mid; } } }
- 作者:程序员小舟
- 链接:https://codezhou.top/article/%E6%8F%92%E5%80%BC%E6%9F%A5%E6%89%BE%E7%AE%97%E6%B3%95
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议,转载请注明出处。