顺序文件的基本概念与查找算法

其中，pi 为查找第 i 个记录的概率，ci 为查找第 i 个记录所进行过的关键字的比较次数。

对于具有 n 个记录的顺序文件，若查找概率相等，则有

故算法的时间复杂度为 O(n)。

顺序查找法的优点和缺点

优点：

1. 查找原理和过程简单，易于理解；
2. 对于被查找对象的排列次序没有限制。

缺点：

1. 查找的时间效率低。

排序连续顺序文件的折半查找法（二分查找法）

核心思想

将要查找的关键字值与当前查找范围内位置居中的记录的关键字的值进行比较。 若匹配，则查找成功，给出被查到记录在文件中的位置，查找结束。 若要查找的关键字值小于位置居中的记录的关键字值，则到当前查找范围的前半部分重复上述查找过程，否则，到当前查找范围的后半部分重复上述查找过程，直到查找成功或者失败。 若查找失败，则给出信息 0。

为实现二分查找法，需要几个变量，如下： n ：排序连续顺序文件中记录的个数 low：当前查找范围内第一个记录在文件中的位置。初值 low=1 high：当前查找范围内最后那个记录在文件中的位置。初值 high=n mid：当前查找范围内位置居中的那个记录的位置， mid 初值为：

((low+high)/2 向下取整)

查找失败的标志为 low > high

非递归算法的 C 语言实现

int BINSEARCH1(keytype key[], int n, keytype k) {
    int low=1, high=n, mid;
    while(low<=high){
        mid=(low+high)/2; // 向下取整
        if(key[mid]==k) return mid; // 查找成功
        if(k>key[mid]) low=mid+1; // 准备查找后半部分
        else high=mid-1; // 准备查找前半部分
    }
    return 0; // 查找失败
}

递归算法的 C 语言实现

int BINSEARCH2(keytype key[], int low, int high, keytype k) {
    int mid;
    if(low>high) return 0;
    else{
        mid=(low+high)/2;
        if(key[mid]==k) return mid;
        else if(k<key[mid]) return BINSEARCH2(key,low,mid-1,k);
        else return BINSEARCH2(key,mid+1,high,k);
    }
}

查找效率

若把当前查找范围内居中的记录的位置作为根结点，前半部分与后半部分的记录的位置分别构成根结点的左子树与右子树，则由此得到一棵称为' 判定树'的二叉树，利用它来描述折半查找的过程。如下图：

成功的查找过程正好等于走了一条从根结点到被查找结点的路径，经历的比较次数恰好是被查找结点在二叉树中所处的层次数！

基于此，二分查找的 ASL 计算如下：

二分查找算法的优点和缺点

优点：

1. 查找原理和过程简单，易于理解。
2. 查找的时间效率较高。

缺点：

1. 要求文件的记录按照关键字值有序排列；
2. 对于文件，只适用于排序连续顺序文件。

为了保持文件为排序顺序文件，在文件中插入和删除记录时需要移动大量的其它记录，所以折半查找方法适用于一经建立就很少改动、而又经常需要查找的文件。

Q：在线性表中采用折半查找方法查找数据元素，该线性表应该满足什么条件？ A：1、数据元素按值有序排列；2、必须采用顺序存储结构。

链接顺序文件的查找

链结点构造

链结点构造及文件整体构造如下：

C 语言实现如下：

typedef struct node {
    keytype key;
    rectype rec;
    struct node *link;
} *KeyLink;

非递归查找算法实现如下：

KeyLink SEARCH1(KeyLink F, keytype k) {
    KeyLink p;
    p=F;
    while(p!=NULL){
        if(p->key==k) return p; /* 查找成功 */
        p=p->link;
    }
    return NULL; /* 查找失败 */
}

递归算法实现如下：

KeyLink SEARCH2(KeyLink F, keytype k) {
    if(F!=NULL)
        if(F->key==k ) return F; /* 查找成功 */
        else return SEARCH2(F->link, k );
    return NULL; /* 查找失败 */
}