静态查找表算法

数据结构

查找在数据结构中十分常见，查找某个元素是否在某个集合之中，并且通常伴随着插入与删除操作，而查询之后是否还有其他动作，将查询分为静态查询和动态查询；
而查找的对象——由具有同一类型（属性）的数据元素（记录）组成的集合，则对应着静态查找表和动态查找表；今天，我们讲讲两个静态查找表的方法——斐波那契查找与分块查找。

斐波那契查找

Screenshot from 2017-12-03 16-54-01

利用斐波那契查找的一项重要准则就是数据元素的个数一定要满足{F[k]-1}，长度必须是某一个斐波那契数减一，只有这样，才能使左子列表的元素个数为F[k-1]-1，右子列表的元素个数为F[k-2]-1，然后左、右子列表又可以继续递归的进行斐波那契查找，而斐波那契查找其实和二分查找很是类似，只是中间的mid值从二分法的（low+high）/2变成了mid=low+F[k-1]-1（以相对low 偏移量F(i-1)-1 取中点）。之所以会出现斐波那契查找法，由于当时计算机计算乘除法的法则不是目前的按位进行位移运算，效率低下，而斐波那契查找法仅仅设计加减法，效率相比有乘除法的二分查找较为高效。

斐波那契查找的算法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int get_fei(int k) {
     return fei[k];
}
bool FibonaqiLook(int a[], int n, int k, int low, int high) {
     int mid = low +get_fei(k -1)-1
     if(low > high)
           return false;
     if(n == a[mid])
           return true;
     if(n > a[mid])
           return FibonaqiLook(int a[],int n, k -2, mid +1, high)
     if(n < a[mid])
           return FibonaqiLook(int a[],int n, k -1, low, mid -1)
}

分块查找

分块查找，其实就是把顺序查找分为几个小部分进行小模块的顺序查找。那么分为小模块的标准是什么呢？其标准就是前一模块的最大关键字要小于后一模块的最小关键字（关键字就是该模块中的元素）。例如下图就是一个分块查找的数组结构图：

Screenshot from 2017-12-03 17-47-20

比如我们要查找一个元素 [5]，想知道这个元素是不是在我要查的表中，首先，我先用元素[5]去和分块表的元素进行比较，发现[5]这个元素小于[13]这个元素，那么可能这个元素在下标为[0-3)的整数区间中，然后在顺序查找这个区间的元素，看是否有与之匹配的元素。

分块查找的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
* a[] 查找表
* std_key[] 分块表(key 数组)
* std_value[] 分块表(value 数组)
* n 待查找元素
*/

void Fenkuai(int a[], int n, int std_value[], int std_key[]) {
    int i;
    for(i =0; i < std_value.length; i ++){
        if(n <= std_value[i])
            break;
    }
    int high = std_key[i], low;
    if(i - 1 > 0)
        low = std_key[i - 1];
    else
        low = 0;
    for(i = low; i <= high; i ++){
        if(a[i]== n)
            return true;
    }
    return false;
}