0


【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. 注意:对于线性表的链式存储只能使用顺序查找

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

标签: 算法 数据结构 c++

本文转载自: https://blog.csdn.net/m0_62159662/article/details/126116877
版权归原作者 东非不开森 所有, 如有侵权,请联系我们删除。

“【21天算法挑战赛】查找算法&mdash;&mdash;顺序查找”的评论:

还没有评论