(精华)2020年8月28日 数据结构与算法解析(插值查找)

插值查找是二分查找的更高效版本，它不会每次按2平分原问题规模，而是应用一个技巧来尽快的接近目标关键字。

示例

public class Program {

    public static void Main(string[] args) {
        int[] array = { 8, 11, 21, 28, 32, 43, 48, 56, 69, 72, 80, 94 };

        Console.WriteLine(InterpolationSearch(array, 80, 0, array.Length - 1));

        Console.ReadKey();
    }

    private static int InterpolationSearch(int[] array, int key, int low, int high) {
        if (low > high) return -1;
        var mid = (int)(low + ((double)key - array[low]) / 
            (array[high] - array[low]) * (high - low));
        if (array[mid] == key)
            return mid;
        else if (array[mid] > key)
            return InterpolationSearch(array, key, low, mid - 1);
        else
            return InterpolationSearch(array, key, mid + 1, high);
    }

}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
 

在最坏的情况下插值查找的时间复杂度为： O(log(logn)) 。

文章来源: codeboy.blog.csdn.net，作者：愚公搬代码，版权归原作者所有，如需转载，请联系作者。

原文链接：codeboy.blog.csdn.net/article/details/108277110