8.1 静态查找

一、顺序查找

将查找表作为一个线性表(顺序表/链表)，依次用查找条件中给定的值与查找表中数据元素的关键字值进行比较.

一般线性表的顺序查找是从线性表的一端开始,逐个检查关键字是否满足给定的条件.

typedef struct table { // 查找表的数据结构
    ElemType *elem;    // 元素存储空间基址
    int length;        // 表的长度
}SSTable;
int Seq_Search(SSTable ST, ElemType key)
{
    ST.elem[0].key = key;  // 设置监视哨兵,查找失败返回0
    for(auto i = ST.length; ST.elem[i].key != key; -- i)
        return i;          // 从后往前找,找到返回key对应下标,找不到返回0
}

“哨兵” ST.elem[0]的作用是：使循环不必判断数组是否会越界.

平均查找长度分析：

(1)查找成功的平均查找长度
对于有 n 个元素的表,给定值key与第 i 个元素相等,即定位第 i 个元素时,需进行 n-i+1次关键字的比较,即,查找成功时,顺序查找的平均长度为

当每个元素的查找概率相等,即时,有,

(2)查找不成功时的平均查找长度
查找不成功时,每个元素都查找到第0个元素,比较次数是 n+1,则

(3)考虑两种情况
每个记录的查找概率为,则

顺序查找的时间复杂度即为查找长度的数量级,时间复杂度为

二、二分查找

二分查找要求查找表用顺序存储结构存放且各数据元素按关键字有序（升序或降序）排列,即只能对有序顺序表进行查找(二分查找不适合无序顺序表和链表).

(1)基本思想：
①首先以整个查找表作为查找范围，取中间元素作为比较对象,

• 若给定值与中间元素的关键字相等，则查找成功；
• 若给定值小于中间元素的关键字，则在中间元素的左半区继续查找；
• 若给定值大于中间元素的关键字，则在中间元素的右半区继续查找

②重复上述查找过程，直到查找成功；或越界(left > right)，所查找的区域无该元素，查找失败.

(2)特点：每次都去除当前区间的一半元素.

(3)代码：

int binarySearch(int seq[], int left, int right, int x)
{
    int mid;
    while (left <= right){
        mid = (left + right) / 2;
        if (seq[mid] == x)    return mid;
        else if (seq[mid] > x)    right = mid - 1;
        else    left = mid + 1;
    }
    return -1;
}

(4)表长固定的平均查找长度分析

二叉查找的判定树：把当前查找区间中的中间位置上的记录作为树根，左子表和右子表中的记录分别作为根的左子树和右子树。

例：求在等概率查找表中元素时，查找成功和不成功的平均查找长度。

解，设13个元素的有序表为：

建树：
① 由 可知，根结点 K7 的左子树下标范围为0~5，右子树下标范围为7~12；
② 由 可知，根结点 K7 的左子树的根结点为 K3，K3 左子树的下标范围为0~1，右子树下标范围为3~5；
③ 由 可知，根结点 K7 的右子树的根结点为 K10，K10 左子树的下标范围为7~8，右子树下标范围为10~12；
④ 由 可知，根结点 K3 的左子树的根结点为 K1，K1 左子树为空，右子树下标范围为1，即 K2；
⑤ 由 可知，根结点 K3 的右子树的根结点为 K5，K5 左子树的下标范围为3，即 K4，右子树下标范围为5，即 K6；
⑥ 由 可知，根结点 K10 的左子树的根结点为 K8，K8 左子树为空，右子树下标范围为8，即 K9；
⑦ 由 可知，根结点 K10 的右子树的根结点为 K12，K12 左子树的下标范围为10，即 K11，右子树下标范围为12，即 K13；

查找成功时，每个结点的比较次数为：

查找不成功时，空指针的比较次数为

（5）一般情况的平均查找分析

三、分块查找

（1）概念：分块查找也叫索引顺序查找，将查找表分为若干子块，再建立一个索引表，索引表按关键字有序排列。

（2）特点：
① 块内元素无序；
② 块之间有序；
③ 每一个块中的最大关键字小于下一个块中所有记录的关键字；
④ 索引表中的每个元素含有各块的最大关键字和各块中第一个元素的地址。

（3）查找过程
① 在索引表中确定待查记录所在的块（顺序查找或二叉查找）；
② 在块内顺序查找。