顺序文件是指物理结构中记录排列次序与逻辑结构一致的文件，分为连续顺序文件和链接顺序文件。连续顺序文件支持顺序查找和折半查找，折半查找效率高但要求数据有序且适用于静态文件。链接顺序文件通过指针连接记录，查找需遍历链表。文中提供了基于 C 语言的查找算法实现及复杂度分析。
在物理结构中记录排列的先后次序与在逻辑结构中记录排列的先后次序一致的文件称为顺序文件。
记录的排列按关键字值有序的顺序文件称为排序顺序文件，否则，称为一般顺序文件；（该划分是在逻辑上的划分）
在存储介质上采用连续组织方式的顺序文件称为连续顺序文件；采用链接组织方式的顺序文件称为；（该划分是在物理上的划分）
若排序顺序文件在存储介质上采用连续组织方式，称之为排序连续顺序文件。
从文件的第一个记录开始，将用户给出的关键字值与当前被查找记录的关键字值进行比较，若匹配，则查找成功，给出被查到的记录在文件中的位置，查找结束。若所有 n 个记录的关键字值都已比较，不存在与用户要查的关键字值匹配的记录，则查找失败，给出信息 0。
int SEQSEARCH1(keytype key[], int n, keytype k) {
int i;
for(i=1; i<=n; i++) // 位置从 1 开始
if(key[i]==k) return i;
return 0;
}
int SEQSEARCH2(keytype key[], int n, keytype k, int i) {
if(i>n) return 0;
if(key[i]==k) return i;
return SEQSEARCH2(key,n,k,i+1);
}
// 该函数调用方式如下：
// int pos = SEQSEARCH2(key,n,k,1); // 从 1 开始
平均查找长度 ASL：确定一个记录在文件中的位置所需要进行的关键字值的比较次数的期望值 (平均值)。
对于具有 n 个记录的文件，有
其中，pi 为查找第 i 个记录的概率，ci 为查找第 i 个记录所进行过的关键字的比较次数。
对于具有 n 个记录的顺序文件，若查找概率相等，则有
故算法的时间复杂度为 O(n)。
优点：
缺点：
将要查找的关键字值与当前查找范围内位置居中的记录的关键字的值进行比较。 若匹配，则查找成功，给出被查到记录在文件中的位置，查找结束。 若要查找的关键字值小于位置居中的记录的关键字值，则到当前查找范围的前半部分重复上述查找过程，否则，到当前查找范围的后半部分重复上述查找过程，直到查找成功或者失败。 若查找失败，则给出信息 0。
为实现二分查找法，需要几个变量，如下： n ：排序连续顺序文件中记录的个数 low：当前查找范围内第一个记录在文件中的位置。初值 low=1 high：当前查找范围内最后那个记录在文件中的位置。初值 high=n mid：当前查找范围内位置居中的那个记录的位置， mid 初值为：
((low+high)/2 向下取整)
查找失败的标志为 low > high
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; // 查找失败
}
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 计算如下：
优点：
缺点：
为了保持文件为排序顺序文件，在文件中插入和删除记录时需要移动大量的其它记录，所以折半查找方法适用于一经建立就很少改动、而又经常需要查找的文件。
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; /* 查找失败 */
}
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online