【21天算法挑战赛】查找算法——顺序查找

💬💬作者有话想说：

💟作者简介：我目前是一个准大二学生，现在不敢说自己擅长什么，但是我想通过自己的学习努力让自己的技术、知识都慢慢提升，希望我们一起学习呀~💜💜💜

☂️兴趣领域：目前偏向于前端学习 算法学习💜💜💜

🎬活动地址：21天学习挑战赛

💜有话想说：写博客、记笔记并不是一种自我感动，把学到的东西记在脑子里才是最重要的，在这个过程中，不要浮躁，希望我们都可以越来越优秀！💜💜💜

🪀语言说明：代码实现我会用Python/C++~

顺序查找

一、普通版顺序查找

1.1.顺序查找思路：

💡💡思路：

• 从数组的一边开始，逐个进行元素的比较，
• 如果与给定的待查找元素相同，则查找成功；
• 如果整个扫描结束后，仍未找到相匹配的元素，则查找失败。

1.2.时间复杂度

.时间复杂度：O(n)

⭐⭐说明：

1. 顺序查找在最坏的情况下遍历整个数组，此时没有找到目标key值，为一次完整的循环，时间复杂度为O(n)
2. 顺序查找在最好的情况下是第一次就找到了目标key值，时间复杂度为O(1)
3. 综合情况分析，顺序查找的时间复杂度为O(n)

1.3.空间复杂度

空间复杂度：O(1)

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

1.4.代码实现

C++代码实现：

#include<iostream>usingnamespace std;#defineLen8int arr[Len+1]={5,7,23,9,45,57,15,33};intSeqSearch(int s[],int n,int key){int i;for(i=0; s[i]!=key; i++);//空循环，不能忘记加；if(i < n){return i;}else{return-1;//返回失败标志值}}intmain(){int key, i, temp;
    arr[Len]= key;
    temp =SeqSearch(arr, Len, key);}

Python代码实现：

arr =[1,3,5,4,2,4,6,5,1]
key =int(input())for i inrange(len(arr)):#顺序遍历列表if arr[i]== key:print(i)break#保证只输出第一个位置就跳出遍历循环#关键字不存在于列表中print(-1)

二、顺序查找改进版

2.1.改进版思路

💡💡思路：

顺序查找改进：设置“哨兵”，就是待查值，放在查找方向的尽头处，免去了每一次比较后都要判断查找位置是否越界。

2.2.复杂度

复杂度同上

2.3.代码实现

intSeqSearch2(int r[],int n,int k){int i = n; 
     r[0]= k;//基本方法0位置空出来//此处将0位置放置要查找的值while(r[i]!= k)//要么在1--n处找到，要么在0处出while循环
        i--;return i;}//若i==0则未查找到

三、优缺点

1. 顺序查找的缺点：当线性表的表长过于长时，平均查找长度较大，效率低。
2. 顺序查找的优点：对顺序表中数据元素的存储没有要求，顺序存储和链式存储均可。
3. 注意：对于线性表的链式存储只能使用顺序查找

算法会持续更新，一起学习吧~💜💜