查找算法——顺序查找

一、普通版顺序查找

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>
using namespace std;

#define Len 8
int arr[Len+1] = {5, 7, 23, 9, 45, 57, 15, 33};
int SeqSearch(int s[], int n, int key)
{
    int i;
    for(i=0; s[i]!=key; i++)
        ; //空循环，不能忘记加；
    if(i < n){
    return i;}
    else{
    return -1; //返回失败标志值}
}
int main()
{
    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 in range(len(arr)): #顺序遍历列表
    if arr[i] == key:
        print(i)
        break #保证只输出第一个位置就跳出遍历循环
#关键字不存在于列表中
print(-1)

二、顺序查找改进版

2.1.改进版思路

💡💡思路：

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

2.2.复杂度

复杂度同上

2.3.代码实现

int SeqSearch2(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. 顺序查找的缺点：当线性表的表长过于长时，平均查找长度较大，效率低。

1. 顺序查找的优点：对顺序表中数据元素的存储没有要求，顺序存储和链式存储均可。
2. 注意：对于线性表的链式存储只能使用顺序查找

_