数据结构-静态查找表查找方法

青旅半醒 2023-05-31 10:22 6阅读 0赞

> **1.顺序查找**

从表的一端开始，逐个将记录的关键字和给定值比较，若找到一个记录的关键字与给定值相等，则查找成功；若整个表中记录均比较过，仍未找到关键字等于给定值的记录，则查找失败。

**缺点：**查找表的长度越长，查找效率越低。

**优点：**简单、适应面广，对查找表结构没有要求，对顺序存储和链式存储都适用。

> **2.折半查找**

设查找表元素存储在一维数组r\[1,…,n\]中，在表中的元素已经**按关键字递增方式排序的**情况下，

进行折半查找的方法是：首先将待查元素的关键字（key）值与表r中间位置上（下标为mid）记录的关键字关键字进行比较，

*  若相等，则查找成功；
 *  若key>r\[mid\].key,则说明待查记录只可能在后半个子表r\[mid+1,…,n\]中；
 *  若key<r\[mid\].key，则说明待查记录只可能在前半个子表r\[1,…,mid-1\]中；

这样逐步缩小范围，直到查找成功或子表为空时失败为止。

//递增的方式排序，则折半查找的算法为
    //在数组r[low...high],在数组r中找值为key的元素
    int Bsearch(int r[],int low,int high,int key)
    {
        int mid;
        while(low <= high)
        {
            mid = (low + high)/2;
            if(key == r[mid])
                return mid;
            else if(key < r[mid])
                high = mid-1;
            else
                low = mid+1;
        }
        return -1;
    }
    
    //折半查找，递归算法
    int Bsearch_rec(int r[],int low,int high,int key)
    {
        int mid;
        if(low <= high)
        {
            mid = (low + high)/2;
            if(key == r[mid])
                return mid;
            else if(key < r[mid])
                return Bsearch_rec(r,low,mid-1,key);
            else
                return Bsearch_rec(r,mid+1,high,key);
        }
        return -1;
    }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d6ejk1MzIwMDQ2Mw_size_16_color_FFFFFF_t_70][] 带11个结点的折半查找判定树

折半查找的过程可以用一颗二叉树来描述，以当前查找区域间的中间位置序号作为根，左半个子表和右半个子表中的记录序号分别分别作为根的左子树和右子树上的结点，这样构造的二叉树称为**折半查找判定树**，从树上可以看出：

查找成功时，折半查找的过程恰好走了一条从根结点到被查找结点的路径，与关键字进行比较的次数即为被查找结点在树中的层数。因此，折半查找判定树在查找成功时进行比较的关键字个数最多不超过树的深度，而具有n个结点的判定树的深度为![\\left \\lfloor \\log\_\{2\}n \\right \\rfloor+1][left _lfloor _log_2_n _right _rfloor_1]；所以折半查找在查找成功时和给定值进行比较的关键字个数最多为![\\left \\lfloor \\log\_\{2\}n \\right \\rfloor+1][left _lfloor _log_2_n _right _rfloor_1]。

*  优点：查找效率更高，但它要求查找表进行顺序存储并按关键字进行排序。
 *  缺点：对表进行插入或删除时，需要移动大量元素。
 *  适用：表不易变动，且又经常进行查找的情况

> ** 3.分块查找**

分块查找又称为**索引顺序查找**，是对顺序查找方法的一种改进，其效率介于顺序查找和折半查找之间。

在分块查找过程中，首先将表分成若干块，每一块的关键字不一定有序，但块之间之间是有序的，即后一块中所有记录的关键字均大于前一块中最大的关键字。此外，还建立了一个“索引表”，索引表按关键字有序。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d6ejk1MzIwMDQ2Mw_size_16_color_FFFFFF_t_70 1][] 分块查找表及其索引表

**查找关键字39的具体位置**：将表分为三个子表，首先将39和最大关键字进行比较，介于23<39<49之间，可以确定，如果39存在，肯定在第二个子表中；从第二个子表的起始位置查找，从34开始起进行顺序查找，一直查找到第二个子表结尾61。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d6ejk1MzIwMDQ2Mw_size_16_color_FFFFFF_t_70]: /images/20230531/5f85fee1ff9245d7863937a27f97edbf.png
[left _lfloor _log_2_n _right _rfloor_1]: https://private.codecogs.com/gif.latex?%5Cleft%20%5Clfloor%20%5Clog_%7B2%7Dn%20%5Cright%20%5Crfloor&plus;1
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d6ejk1MzIwMDQ2Mw_size_16_color_FFFFFF_t_70 1]: /images/20230531/6aaa0296d2984771b2cdbbe88c6c8acd.png