type
status
date
slug
summary
tags
category
icon
password

1、插值查找原理介绍

  1. 插值查找算法类似于二分查找,不同的是插值查找每次从自适应mid处开始查找。
  1. 将折半查找中的求mid 索引的公式 , low 表示左边索引left, high表示右边索引right,key 就是前面我们讲的 findVal
    1. notion image
  1. 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. 举例说明插值查找算法 1-100 的数组
    1. notion image

      2、插值查找案例应用

      请对一个有序数组进行插值查找 {1,8, 10, 89, 1000, 1234} ,输入一个数看看该数组是否存在此数,并且求出下标,如果没有就提示"没有这个数"。

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;       }   } }
 
单向链表的java实现 详细讲解插入排序 java详细讲解