常用的7大查找算法之三：插值查找算法（自适应有序）

2017-04-23 17:33 阅读 3,508 次 评论 0 条

1.查找算法概述

查找是在大量的信息中寻找一个特定的信息元素，在计算机应用中，查找是常用的基本运算，例如编译程序中符号表的查找。本文简单概括性的介绍了常见的七种查找算法，说是七种，其实二分查找、插值查找以及斐波那契查找都可以归为一类——插值查找。插值查找和斐波那契查找是在二分查找的基础上的优化查找算法。树表查找和哈希查找会在后续的博文中进行详细介绍。

 

（1）查找定义

根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素（或记录）。

 

（2）查找算法分类

1）静态查找和动态查找

注：静态或者动态都是针对查找表而言的。动态表指查找表中有删除和插入操作的表。

2）无序查找和有序查找

无序查找：被查找数列有序无序均可；

有序查找：被查找数列必须为有序数列。

 

（3）查找算法分析

平均查找长度（Average Search Length，ASL）：需和指定key进行比较的关键字的个数的期望值，称为查找算法在查找成功时的平均查找长度。

对于含有n个数据元素的查找表，查找成功的平均查找长度为：ASL = Pi*Ci的和。

Pi：查找表中第i个数据元素的概率。

Ci：找到第i个数据元素时已经比较过的次数。

 

2.插值查找

（1）插值查找说明

在介绍插值查找之前，首先考虑一个新问题，为什么上述算法一定要是折半，而不是折四分之一或者折更多呢？

打个比方，在英文字典里面查“apple”，你下意识翻开字典是翻前面的书页还是后面的书页呢？如果再让你查“zoo”，你又怎么查？很显然，这里你绝对不会是从中间开始查起，而是有一定目的的往前或往后翻。

同样的，比如要在取值范围1 ~ 10000 之间 100 个元素从小到大均匀分布的数组中查找5， 我们自然会考虑从数组下标较小的开始查找。

经过以上分析，折半查找这种查找方式，不是自适应的（也就是说是傻瓜式的）。二分查找中查找点计算如下：

mid=(low+high)/2, 即mid=low+1/2*(high-low);

通过类比，我们可以将查找的点改进为如下：

mid=low+(key-a[low])/(a[high]-a[low])*(high-low)，

也就是将上述的比例参数1/2改进为自适应的，根据关键字在整个有序表中所处的位置，让mid值的变化更靠近关键字key，这样也就间接地减少了比较次数。

 

（2）基本思想

基于二分查找算法，将查找点的选择改进为自适应选择，可以提高查找效率。当然，插值查找也属于有序查找。

注：对于表长较大，而关键字分布又比较均匀的查找表来说，插值查找算法的平均性能比折半查找要好的多。反之，数组中如果分布非常不均匀，那么插值查找未必是很合适的选择。

 

（3）复杂度分析

查找成功或者失败的时间复杂度均为O(log2(log2n))。

 

（4）插值查找C语言源代码

插值查找C/C++源代码
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/**
* 算法君：一个专业的算法学习分享网站
* 算法君：专业分享--数据剖析--算法精解
* 算法君：http://www.suanfajun.com
*/
 
 
#include<stdio.h>
//插值查找算法--有序查找
//基本思路：二分查找改进版，只需改一行代码。
//        mid=low+(key-a[low])/(a[high]-a[low])*(high-low)
int insertSearch(int *sortedSeq, int seqLength, int keyData)
{
    int low = 0, mid, high = seqLength - 1;
 
    while (low <= high)
    {
        mid = low + (keyData - sortedSeq[low]) / (sortedSeq[high] - sortedSeq[low]);
        if (keyData < sortedSeq[mid])
        {
            high = mid - 1;//是mid-1，因为mid已经比较过了
        }
        else if (keyData > sortedSeq[mid])
        {
            low = mid + 1;
        }
        else
        {
            return mid;
        }
    }
    return -1;
}
 
int main()
{
    int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
    int location;
    int target = 4;
    location = insertSearch(array, 9, target);
    printf("目标位置：%d\n", location);
    return 0;
}

（5）插值查找C++语言源代码

插值查找C++语言源代码
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
/**
* 算法君：一个专业的算法学习分享网站
* 算法君：专业分享--数据剖析--算法精解
* 算法君：http://www.suanfajun.com
*/
 
 
#include<iostream>
using namespace std;
 
//插值查找算法--有序查找
//基本思路：二分查找改进版，只需改一行代码。
//        mid=low+(key-a[low])/(a[high]-a[low])*(high-low)
int insertSearch(int *sortedSeq, int seqLength, int keyData)
{
    int low = 0, mid, high = seqLength - 1;
 
    while (low <= high)
    {
        mid = low + (keyData - sortedSeq[low]) / (sortedSeq[high] - sortedSeq[low]);
        if (keyData < sortedSeq[mid])
        {
            high = mid - 1;//是mid-1，因为mid已经比较过了
        }
        else if (keyData > sortedSeq[mid])
        {
            low = mid + 1;
        }
        else
        {
            return mid;
        }
    }
    return -1;
}
 
int main()
{
    int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
    int location = -1;
    int target = 4;
    location = insertSearch(array, 9, target);
    cout<< "目标位置：" << location<< endl;
    return 0;
}

 

 

版权声明：本文著作权归原作者所有，欢迎分享本文，谢谢支持！
转载请注明：常用的7大查找算法之三：插值查找算法（自适应有序） | 算法君
分类：数据结构 标签：,

发表评论


表情