03.插值查找元素

归并排序

  • 1.基本思想
  • 2.排序过程
  • 3.代码实现
  • 4.如何优化
  • 5.复杂度
  • 6.使用场景

1.基本思想

  • 二分法查然效率很高，但我们为什么要和中间的值进行比较，如果我们和数组1/4或者3/4部分的值进行比较可不可以呢，对于一个要查找的数我们不知道他大概在数组的什么位置的时候我们可以使用二分法进行查找。
  • 但如果我们知道要查找的值大概在数组的最前面或最后面的时候使用二分法查找显然是不明智的。比如我们查字典的时候如果是a或者b开头的我们一般会在前面找，如果是y或者z开头的我们一般偏向于往后面找，这个时候如果我们使用二分法从中间开始找显然是不合适的。

2.排序过程

  • 之前二分法查找的时候我们比较的是中间值，mid=low+1/2*(high-low);但插值查找的时候我们比较的不是中间值，是mid=low+(key-a[low])/(a[high]-a[low])*(high-low)，我们来看下插值查找的代码。

3.代码实现

  • 代码如下所示
    public static int insertSearch(int[] array, int key) {
    return search(array, key, 0, array.length - 1);
}

private static int search(int[] array, int key, int left, int right) {
    while (left <= right) {
        if (array[right] == array[left]) {
            if (array[right] == key)
                return right;
            else return -1;
        }
        int middle = left + ((key - array[left]) / (array[right] - array[left])) * (right - left);
        if (array[middle] == key) {
            return middle;
        }
        if (key < array[middle]) {
            right = middle - 1;
        } else {
            left = middle + 1;
        }
    }
    return -1;
}
  • 和二分法查找代码很相似，只不过计算middle的方式不一样。再来看一下递归的版本。
    public static int insertSearch(int[] array, int key) {
    return search2(array, key, 0, array.length - 1);
}

private static int search2(int array[], int key, int left, int right) {
    if (left > right)
        return -1;
    if (array[right] == array[left]) {
        if (array[right] == key)
            return right;
        else return -1;
    }
    int mid = left + (key - array[left]) / (array[right] - array[left]) * (right - left);
    if (array[mid] == key)
        return mid;
    if (array[mid] > key)
        return search2(array, key, left, mid - 1);
    return search2(array, key, mid + 1, right);
}

4.如何优化

5.复杂度

  • 时间复杂性：如果元素均匀分布，则O(log(logn))，在最坏的情况下可能需要 O(n)。
  • 空间复杂度：O(1)。

6.使用场景

关于其他内容介绍

01.关于博客汇总链接

02.关于我的博客

  • 我的个人站点：
  • github：https://github.com/yangchong211
  • 知乎：https://www.zhihu.com/people/yang-chong-69-24/pins/posts
  • 简书：http://www.jianshu.com/u/b7b2c6ed9284
  • csdn：http://my.csdn.net/m0_37700275
  • 喜马拉雅听书：http://www.ximalaya.com/zhubo/71989305/
  • 开源中国：https://my.oschina.net/zbj1618/blog
  • 泡在网上的日子：http://www.jcodecraeer.com/member/content_list.php?channelid=1
  • 邮箱：yangchong211@163.com
  • 阿里云博客：https://yq.aliyun.com/users/article?spm=5176.100- 239.headeruserinfo.3.dT4bcV
  • segmentfault头条：https://segmentfault.com/u/xiangjianyu/articles
贡献者: yangchong211