九种查找算法-顺序查找

时间、空间复杂度比较

查找算法	平均时间复杂度	空间复杂度	查找条件
顺序查找	O(n)	O(1)	无序或有序
二分查找（折半查找）	O(log2n)	O(1)	有序
插值查找	O(log2(log2n))	O(1)	有序
斐波那契查找	O(log2n)	O(1)	有序
哈希查找	O(1)	O(n)	无序或有序
二叉查找树（二叉搜索树查找）	O(log2n)
红黑树	O(log2n)
2-3树	O(log2n - log3n)
B树/B+树	O(log2n)

顺序查找

顺序查找也叫线性查找

查找过程：从列表中的第一个元素开始，逐个元素进行比较，如果找到相等的元素，则 查找成功 ，如果直至表中最后一个记录数与目标值都不相等，则表示 查找失败 。
顺序查找算法适用于绝大多数场景，既可以在有序序列中查找目标元素，也可以在无序序列中查找目标元素。

算法效率
算法效率分析分为两种：第一种是时间效率，第二种是空间效率。时间效率被称为时间复杂度，而空间效率被称作空间复杂度。 时间复杂度主要衡量的是一个算法的运行速度，而空间复杂度主要衡量一个算法所需要的额外空间。
 

算法思路：

对于任意一个序列，从一端开始，顺序扫描，依次将扫描到的结点关键字与给定值k相比较，若相等则表示查找成功；若扫描结束仍没有找到关键字等于k的结点，表示查找失败。

代码：

#include <stdio.h>
#include <stdlib.h>
#define keyType int
//2020.05.24
typedef struct
{keyType key;//查找表中每个数据元素的值
}ElemType;typedef struct
{ElemType *elem;//存放查找表中数据元素的数组int length;//记录查找表中数据的总数量
}SSTable;//创建查询数据
void Create(SSTable **st,int length)
{(*st)=(SSTable*)malloc(sizeof(SSTable));(*st)->length=length;(*st)->elem =(ElemType*)malloc((length+1)*sizeof(ElemType));printf("输入表中的数据元素：\n");//根据查找表中数据元素的总长度，在存储时，从数组下标为 1 的空间开始存储数据for (int i=1; i<=length; i++){scanf("%d",&((*st)->elem[i].key));}
}//顺序查找函数，其中key为要查找的元素
int Search_seq(SSTable *str,keyType key)
{//str->elem[0].key=key;//将关键字作为一个数据元素存放到查找表的第一个位置，起监视哨的作用int len = str->length;//从最后一个数据元素依次遍历，一直遍历到数组下标为0for(int i=1; i<len+1; i++)   //创建数据从数组下标为1开始，查询也从1开始{if(str->elem[i].key == key){return i;}}//如果 i=0，说明查找失败；查找成功返回要查找元素key的位置ireturn 0;
}int main()
{SSTable *str;int num;printf("请输入创建数据元素的个数：\n");scanf("%d",&num);Create(&str, num);getchar();printf("请输入要查找的数据：\n");int key;scanf("%d",&key);int location=Search_seq(str, key);if (location==0) {printf("查找失败");}else{printf("要查找的%d的顺序为：%d",key,location);}return 0;
}

效率分析
时间复杂度

最坏的情况
最坏的情况就是完整的遍历了整个集合，也并未找到目标的key，此时循环被完整的执行，循环执行次数与n相关，所以时间复杂度为O(n)。

最好的情况
最好的情况就是第一次就找到了元素，此时的时间复杂度为常数级O(1)。

平均情况
综合两种情况，顺序查找的时间复杂度为O(n)，属于查找较慢的算法。

空间复杂度
由于算法不会改变原有的元素集合，只需要一个额外的变量控制索引变化，所以空间复杂度为常数级：O(1)

顺序查找的优缺点

1）缺点：查找效率较低，特别是当待查找集合中元素较多时，不推荐使用顺序查找。
2）优点：算法简单而且使用面广。