插值查找

代码实现

  1. /**
  2.  * @author laoduan
  3.  * @create 2020-05-10-18:30
  4.  */
  5. public class InsertValueSearch {
  6.     public static void main(String[] args) {
  8.         int [] arr = new int[100];
  9.         for(int i = 0;i<100;i++){
  10.             arr[i]= i+1;
  11.         }
  12.     }
  16.     public static int insertValueSearch(int [] arr,int left,int right,int findVal){
  18.         //注意:findVal<arr[0] || findVal>arr[arr.length-1]是必须存在的
  19.         //否则mid可能越界
  20.         if(left>right || findVal<arr[0] || findVal>arr[arr.length-1]){
  21.             return -1;
  22.         }
  23.         int mid = left +(right-left) *(findVal-arr[left])/(arr[right]-arr[left]);
  24.         int midVal =arr[mid];
  26.         if(findVal>midVal){
  27.             //说明应该向右递归
  28.             return insertValueSearch(arr,mid+1,right,findVal);
  29.         }else if(findVal<midVal){
  30.             return insertValueSearch(arr,left,mid-1,findVal);
  31.         }else {
  32.             return mid;
  33.         }
  35.     }
  36. }