作者:[柒号华仔]
个人信条:星光不问赶路人,岁月不负有心人。
个人方向:主要方向为5G,同时兼顾其他网络协议,编解码协议,C/C++,linux,云原生等,感兴趣的小伙伴可以关注我,一起交流。
1. 顺序查找介绍
1.1 定义
查找是指在指定数据组合中找出满足条件的元素个体。顺序查找是按照序列原有顺序对数组进行遍历比较查询的基本查找算法。
顺序查找是最基础也是最简单的查找算法,在需要进行查找时,这是我们的首选方法,只有数据较多,结构复杂,耗时较多需要优化时,我们才会考虑使用其他查找方法。
1.2 基本原理
对于任意一个序列以及一个给定的元素,从第一个序列元素开始,将给定元素与序列中元素依次比较,若某个元素与给定元素相同,则查找成功,否则,若将序列中的元素与给定元素全部比较完,依然无法匹配相同,则查找失败。
比如,拿着一张照片从一个班上找出对应学生,那么长相就是判定值,我们需要一个个学生依次去比对,长相一致则找出了该学生,如果全班都看了一遍,还是没找到,则寻人失败。
1.3 时间复杂度与空间复杂度
顺序查找平均查找长度为 (n + 1) / 2,时间复杂度为 O(n) 。
顺序查找是对数列顺序的比较,没有额外的空间,所以空间复杂度为常数 O(1)。
1.4 优缺点
优点:算法简单,对表中元素排列次序无要求,且对关键字的次序无要求,插入和删除元素都非常方便。
缺点:时间复杂度较大,当数据规模较大时,效率较低。
2. 代码实现
2.1 代码设计
a. 输入需要查找的元素key;
b. 从数组首元素(i=0)开始查找,如果array[i] = key,则查找成功返回i;
c. 否则i加1,继续查找,如果找到数组末尾,依然没找到,则查找失败,返回-1。
2.2 代码实现
#include<stdio.h>
#include<string.h>
int search(int array[],int n,int key)
{
int i;
for(i = 0; i<n; i++){
if(array[i] == key)
return i; //查找成功
}
return -1; //查找失败
}
int main(void)
{
int arr[7] = {62,8,35,22,90,58,6};
int key,ret;
printf("请输入需要查找的数字:");
scanf("%d",&key);
ret = search(arr,sizeof(arr)/4,key);
if(ret < 0)
printf("查找失败\n");
else
printf("该数字为数组第%d个元素\n",ret+1);
return 0;
}
运行结果:
请输入需要查找的数字:58
该数字为数组第6个元素