数据结构之详解有序表查找

曾经终败给现在 2022-09-28 13:24 145阅读 0赞

# 有序表查找 #

*  **二分查找**
 *  **插值查找**
 *  **斐波那契查找**
 *  **性能对比**

## 1、二分查找 ##

> 又称折半查找，它的前提是线性表必须采用顺序存储。基本思想是每一次都去的序列的中间位置的关键字进行比较，然后根据大小进行序列的更新，如此不断循环，直到最后。

1、在有序序列中取中间位置作为比较对象，若待查找对象与该对象相等，则查找成功。

2、若待查找对象小于中间对象，则在中间对象的左半区继续重复步骤1，进行查找。

3、若待查找对象大于中间对象，则在中间对象的右半区继续重复步骤1，进行查找。

4、不断重复上述过程，直到查找成功，若无相等对象则查找失败。

实现代码如下所示：

int Binary_Search(int *a, int n; int key)
    {
        int low, high, mid;
        low = 1;
        high = n;
        while (low < high)
        {
            mid = (low + high) / 2; //折半，这里每次都取得是中间位置
    
            if (key < a[mid]) //下一次循环，取在中间对象的左半区
                high = mid - 1;
    
            else if (key>a[mid]) //下一次循环，取在中间对象的右半区
                low = mid + 1;
    
            else
                return mid;
        }
        return 0;
    
    }

## 2、差值查找 ##

> 这是一种对二分查找（折半查找）的改进形式，插值查找的每次选取的比较对象不再是序列的正中间位置，而是与待查找的key值有关。

可以进行对比，二分查找的中间位置可以表示为：

![这里写图片描述][SouthEast]

现在的插值查找的位置变成如下形式：

![这里写图片描述][SouthEast 1]

实现代码只需修改一行即可：

mid = mid = low + (high - row)*(key - a[low]) / (a[high] - a[low]); //插值

> 对于表比较长，而关键字又分布比较均匀的查找表来说，插值算法的平均性能会比折半查找要好，但是对于分布比较极端不均匀的数据，插值法不一定是合适的。

## 3、斐波那契查找 ##

> 这是一种利用黄金分割原来来实现查找的方法。

斐波那契数列：

![这里写图片描述][SouthEast 2]

实现代码如下所示：

int Fibonacci_Search(int *a, int n; int key)
    {
        int low, high, mid, i, k;
        low = 1;
        high = n;
        k = 0;
        while (n > F[k] - 1) //计算n位于斐波那契数列中的位置
            k++;
        for (i = n; i < F[k] - 1; i++) //将不满的数值补全
            a[i] = a[n];
    
        while (low < high)
        {
            mid = low + F[k-1]-1;  //计算当前分割符的下标
    
            if (key < a[mid])
            {
                high = mid - 1;
                k = k - 1;
            }
    
            else if (key>a[mid])
            {
                low = mid + 1;
                k = k - 2;
            }
    
            else
            {
                if (mid <= n)
                    return mid;
                else
                    return n;
            }           
        }
        return 0;
    }

![这里写图片描述][SouthEast 3]

> 就平均性能而言，斐波那契查找要优于折半查找，但是如果是最坏的情况，比如key=1.那么始终处于左侧长半区查找，查找效率要低于折半查找。

## 4、性能比较 ##

> 折半查找是进行加法和除法运算（mid=（low+high）/2）,插值查找则进行复杂的四则运算（mid=low+（high-low）\*（key-a\[low\])/(a\[high\]-a\[low\]））, 而斐波那契查找只是进行最为简单的的加减法运算（mid=low+F\[k-1\]-1）, 在海量的数据查找中，会很大程度的影响效率，虽然它们的时间复杂度均为O（logn）。

[SouthEast]: /images/20220708/78705c22dc254e85835f910d406d3e84.png
[SouthEast 1]: /images/20220708/a7a74a1a8eba44bbaa3612d3201bc334.png
[SouthEast 2]: /images/20220708/c8530559c6754181848dd59e56fd0d75.png
[SouthEast 3]: /images/20220708/561b865cf15a4178883b7dfd3d99111f.png