一、定义

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

二、查找算法

1. 顺序查找

1.1 概念

顺序查找适合于存储结构为顺序存储或链接存储的线性表。顺序查找也称为线性查找，属于无序查找算法。从线性表的一端开始，顺序扫描，依次将扫描到的结点关键字与给定值k相比较，若相等则表示查找成功；若扫描结束仍未找到关键字等于k的结点，表示查找失败。

复杂度分析

• 查找成功时的平均查找长度为：（假设每个数据元素的概率相等）
  $ASL = \frac{1}{n}(1 + 2 + 3 + \dots + n) = \frac{n + 1}{2}$
• 当查找不成功时，需要n + 1次比较，时间复杂度为O(n)。
• 因此，顺序查找的时间复杂度为O(n)。

1.2 代码示例

// 顺序查找
int seqSearch(int arr[], int target)
{
    for(int i = 0; i < sizeof(arr); i++)
    {
        if(arr[i] == target){
            return i;
        }
    }
    return -1;
}

2. 二分查找

2.1 概念

• 应用二分查找的序列元素必须是有序的，如果是无序的则要先进行排序操作。
• 二分查找也称为折半查找，属于有序查找算法。用给定值k先与中间结点的关键字比较，中间结点把线性表分成两个子表：
  • 若相等，则查找成功；
  • 若不相等，则根据k与该中间结点关键字的比较结果确定下一步查找哪个子表，这样递归进行，直到查找到或查找结束发现表中没有这样的结点。
• 复杂度分析：最坏情况下，关键词比较次数为log₂(n + 1)，且期望时间复杂度为O(log₂n)。
• 注：折半查找的前提条件是需要有序表顺序存储。对于静态查找表，一次排序后不再变化，折半查找能得到不错的效率。但对于需要频繁执行插入或删除操作的数据集来说，维护有序的排序会带来不小的工作量，那就不建议使用。

2.2 代码示例

// 二分查找
int biSearch(int arr[], int target)
{
    int l = 0;
    int r = sizeof(arr) - 1;
    while (l < r)
    {
        int mid = (l + r) / 2;
        if (arr[mid] < target)
        {
            l = mid + 1;
        }
        else
        {
            r = mid;
        }
    }
    if (arr[l] == target)
    {
        return l;
    }
    return -1;
}

三、课后练习

1. 设有100个数据元素，采用折半搜索时，最大比较次数为（ ）。

{{ select(1) }}

• 6
• 7
• 8
• 10

2. 有一个由4000个整数构成的顺序表，假定表中的元素已经按升序排列，采用二分查找定位一个元素。则最多需要（ ）次比较就能确定是否存在所查找的元素。

{{ select(2) }}

• 11次
• 12次
• 13次
• 14次

3. 对有序数组{5，13，19，21，37，56，64，75，88，92，100}进行二分查找，成功查找元素19的查找长度（比较次数）是（ ）。

{{ select(3) }}

• 1
• 2
• 3
• 4

4. 对有序数组{5，13，19，21，37，56，64，71，88，92，100}进行二分查找，等概率的情况下查找成功的平均查找长度（平均比较次数）是（ ）。

{{ select(4) }}

• 35/11
• 34/11
• 33/11
• 32/11
• 34/10

5. 对长度为3的顺序表进行查找，若查找第一个元素的概率为1/2，查找第二个元素的概率为1/3,查找第三个元素的概率为1/6, 则查找任一元素的平均查找长度为（ ）。

{{ select(5) }}

• 5/3
• 2
• 7/3
• 4/3

6. 具有 12 个关键字的有序表中，对每个关键字的查找概率相同，折半查找算法查找成功的平均查找长度为（ ）。 {{ select(6) }}

• 37/12
• 35/12
• 39/13
• 49/13

7. 只能在顺序存储结构上进行的查找方法是（ ）。

{{ select(7) }}

• 顺序查找
• 二分查找
• 树型查找
• 散列查找