数据结构-06：静态查找

静态搜索表：集合中的结点总数是固定的或者很少发生变化。
动态搜索表：集合中的结点总数是经常在发生变化。
在内存中进行的搜索：重点减少比较、或查找的次数。评价标准：平均搜索长度。
在外存中进行的搜索：重点在于减少访问外存的次数。评价标准：读盘次数。

静态查找的前提是数据集合基本不变化，因此可以为了查找效率提前做一些组织工作，例如排序、建立索引或分块。选择查找算法时先看两个问题：数据是否有序，数据分布是否均匀。有序才能二分；分布均匀时插值查找才可能比二分更快；如果都不满足，顺序查找反而是最稳妥的基线方案。

顺序查找

template <class KEY, class OTHER>
int seqSearch(SET<KEY, OTHER> data[], int size, const KEY &x)
{
    data[0].key = x; // 哨兵：保证循环一定能停下
    for (int i = size; x != data[i].key; --i)
        ; // 实际数据放在data[1]到data[size]
    return i; // 返回0表示查找失败
}

哨兵 data[0].key = x 的作用是消除循环中的越界判断。循环从 size 向前找，只要真实数据中没有目标，最终一定会在 data[0] 停下。返回值为 0 时表示失败，返回正数时表示在对应位置找到。这个技巧牺牲了 0 号单元作为哨兵，使循环体更简洁。

时间复杂度为 $O(n)$ ，其中 $n$ 为数据元素的个数。
推导过程注意分为成功和不成功两部分，两种情况概率相等，同时每个结点搜索成功的概率也相等。

折半查找（二分查找）

template <class KEY, class OTHER>
int binarySearch(SET<KEY, OTHER> data[], int size, const KEY &x)
{
    int low = 0, high = size - 1, mid;
    while (low <= high) {
        mid = low + (high - low) / 2; // 避免low + high在大数组上溢出
        if (data[mid].key == x) return mid;
        else if (data[mid].key < x) low = mid + 1; // 目标只可能在右半区
        else high = mid - 1; // 目标只可能在左半区
    }
    return -1; // 未找到
}

二分查找的循环不变量是：如果目标存在，它一定在当前闭区间 [low, high] 内。每次比较 mid 后，算法都会排除掉一半不可能包含目标的区间。注意二分查找要求数据按关键字有序；如果数组无序，low 和 high 的移动就没有数学依据。

在最坏情况下，二分查找有序表的最大比较次数约为：

$\lfloor \log_2 n \rfloor + 1$

平均情况分析（只考虑查找成功的情况下）：平均查找代价约为 $\log_2(n + 1) - 1$ 。
平均情况分析（考虑成功、非成功查找两种的情况下）：平均查找代价约为 $\log_2 n + \frac{1}{2}$ 。
时间复杂度为 $O(\log n)$ 。

插值查找

适用于数据分布比较均匀的情况，可以快速定位。
查找位置计算公式：

$next = low + \frac{(high - low)(x - data[low])}{data[high] - data[low]}$

如果数组元素是 SET 类型，公式中的 data[low] 和 data[high] 应理解为对应的关键字 data[low].key 与 data[high].key。实际代码中还需要处理 data[high].key == data[low].key 的边界情况，避免除零。