目录
1. 顺序查找
时间复杂度：O(n)
存储结构：
顺序查找可适用于线性表的顺序存储和链式存储。
顺序查找的过程：
从表的一端开始，依次将记录的关键字和给定值进行比较，若某个记录的关键字和给定值相等，则查找成功；反之，若扫描完整个表后，仍未找到关键字和给定值相等的记录，则查找失败。
数据元素类型定义如下：
typedef struct {
KeyType key; //关键字
InfoType otherinfo; //其他域
}ElemType;-
利用顺序表的实现顺序查找
数据元素类型定义如下：
typedef struct {
KeyType key; //关键字
InfoType otherinfo; //其他域
}ElemType;查找时从后往前开始比较
typedef struct{
ElemType *R; //顺序存储结构的基地址
int length; //表长
}SSTable;int search_Seq(SSTable ST,KeyType key){
for(int i = ST.length; i >= 1; i--){
if(ST.R[i].key == key) return i;
}
return 0;
} -
设置监视哨的顺序查找
改进方法：通过设置监视哨，免去查找过程中每一步都要检测整个表是否查找完毕。
int Search_Seqs(SSTable ST,KeyType key){
ST.R[0] = key;
for(int i = ST.legnth; ST.R[i].key != key; --i) //从后往前找
return i; //如果没找到返回值为 0;
}-
利用链表实现顺序查找
typedef struct LNode{
ElemType data; //数据域
struct Node * next; //指针域
}LNode, * LinkList;LNode * Search_Lin(LinkList L,KeyType key){
LNode * p = L -> next; //p 指向首元结点
while(p != NULL){
if(p -> data == key){
return p;
}
p = p -> next; //指向下一个结点
}
return NULL;
}顺序查找的优缺点
优点：算法简单，对表结构无任何要求，顺序存储或链式存储皆可。同时对表中记录的有序性也没有要求，无论记录是否按关键字有序，均可应用。需注意的是，对线性的链表只能进行顺序查找。
缺点：平均查找长度较大，查找效率较低，当n较大时，不适合采用顺序查找。
2. 折半查找（二分查找）
时间复杂度：O(log2n)
对于线性表必须采用顺序存储结构，而且表中元素按照关键字有序排列。
折半查找过程：
从表的中间记录开始，如果给定值和中间记录的关键字相等，则查找成功；
如果给定值大于或这小于中间记录的关键字，则在表中大于或小于中间记录的那一半中查找，这样重复操作，直到查找成功，或者在某一步中查找区间为空，则代表查找失败。
查找区间为空的条件：low > hight
【算法描述】
int Search_Bin(SSTable ST,keyType key) {
int low = 1, high = ST.length;
int mid = (low + high) >> 1;
while(low <= high) {
if(ST.R[mid].key == key) return i;
else if(key < ST.R[mid].key) high = mid - 1;
else low = mid + 1;
}
return 0; //查找失败
}折半查找的优缺点
优点：折半查找效率高于顺序查找，比较次数少，查找效率高。
缺点：只能用于顺序存储的有序表。（折半查找前需要对元素进行排序，如果元素量过大，排序也会消耗大量时力；若插入或删除表中元素，平均比较和移动表中一半的元素也会消耗大量时力。所以折半排序不适用于数据元素经常变动的线性表）
3. 分块查找
分块查找又称索引顺序查找，它吸取了顺序查找和折半查找的优点，既有动态结构，又适于快速查找。
分块查找过程：
分块查找与前两种方法相比，需额外建立一个“索引表”。
将查找表分为若干子表（或称块），对每个子表建立一个索引项。
其中包含两项内容：关键字项（其值为该子表内的最大）和指针项（指示该子表的第一个记录在表中的位置）。
每个索引项构成一个索引表，索引表按关键字有序排列。
块内的元素可以无序，但块间的元素是有序的，又称分块有序。即第一块中最大关键字小于第二块中的所有记录的关键字，第二块中最大关键字小于第三块中的所有记录的关键字，以此类推。
时间复杂度：
分块查找的时间复杂度主要取决于块的数量以及每个块中元素的数量。
在最坏的情况下，即目标元素位于最后一个块中，并且最后一个块中的元素数量最多，分块查找需要遍历所有块，并且对于最后一个块，需要遍历其中的所有元素。
因此，时间复杂度为 O(m + n)，其中 m 是块的数量，n 是所有块中元素的总数。
分块查找的优缺点
优点：在表中插入和删除数据元素，只需找到对应的块，就可在该块中进行插入和删除运算。由于块中是无序的，故插入和删除无需进行大量移动。
缺点：要增加一个索引表的存储空间并对初始索引表进行排序运算。
标签：折半,顺序,线性表,分块,关键字,查找,key From： https://blog.csdn.net/2301_81182847/article/details/144346183