一、算法介绍

1.算法思想

顺序查找也称线性查找，其查找思想非常简单，只需对数组进行遍历并将待查找元素key与数组内元素逐个比较即可，若相同则查找成功返回对应数组下标；若遍历完整个数组也没有找到待查找元素，则说明查找失败，返回-1。

2.算法流程

例：给定一个数组arr[]={2,5,4,8,9,7}，查找元素8，成功返回元素对应数组下标，失败返回-1。

若采用上述示例查找元素10，则通过循环比较完数组arr中6个元素后，仍未找到待查找元素，则退出循环并返回-1。

二、算法实现

1.代码实现

#include<iostream>
using namespace std;int SeqSearch(int* arr, int size, int key) {//顺序查找for (int i = 0; i < size; i++) {if (arr[i] == key) {return i;}}return -1;
}void Test() {//测试函数int arr[] = { 2,5,4,8,9,7 };int length = sizeof(arr) / sizeof(arr[0]);//获取数组内元素个数int key;cout << "请输入待查找元素：";cin >> key;int result = SeqSearch(arr, length, key);//调用顺序查找函数if (result == -1) {cout << endl << "查找失败!" << endl;cout<<"集合中没有待查找元素！" << endl;}else {cout << "查找成功！" << endl;cout << "元素" << key << "所在位置下标为" << result << "!" << endl;}
}int main() {Test();return 0;
}

2.测试用例及结果

arr[]={2,5,4,8,9,7}

查找元素8：

查找元素7：

查找元素10：

三、性能分析

1.时间复杂度

最坏情况：

待查找元素位于集合末尾位置或查找失败时，程序需遍历完整个集合才能退出，此时的循环次数与集合元素个数n有关，所以时间复杂度为O(n)。

最好情况：

最理想的情况就是待查找元素位于集合的第一个位置，程序只需执行一次循环和比较就成功找到待查找元素并返回退出，所以时间复杂度为O(1)。

平均情况：

综合两种情况，顺序查找的时间复杂度为O(n)。

2.空间复杂度

算法中只需设置一个临时变量用于控制循环次数和数组下标变化，没有借助额外的辅助空间，所以空间复杂度为O(1)。

四、优化方案

1.优化思想

考虑到顺序查找的思想是通过顺序比较集合元素的方法进行查找，所以我们可以通过设置两个索引从集合的两边进行同时比较查找，这样每次循环就可以比较淘汰两个元素，从而一定程度上的提高算法效率。

2.代码实现

#include<iostream>
using namespace std;int Optimized_SeqSearch(int* arr, int size, int key) {//顺序查找优化版本int index1 = size - 1;//右侧索引int index2 = 0;//左侧索引while (index2 <= index1) {//相等位置也需要比较if (arr[index1] == key) {return index1;}if (arr[index2] == key) {return index2;}index1--;index2++;}return -1;
}void Test() {//测试函数int arr[] = { 2,5,4,8,9,7 };int length = sizeof(arr) / sizeof(arr[0]);//获取数组内元素个数int key;cout << "请输入待查找元素：";cin >> key;//int result = SeqSearch(arr, length, key);//调用顺序查找函数int result = Optimized_SeqSearch(arr, length, key);//调用顺序查找函数if (result == -1) {cout << endl << "查找失败!" << endl;cout<<"集合中没有待查找元素！" << endl;}else {cout << "查找成功！" << endl;cout << "元素" << key << "所在位置下标为" << result << "!" << endl;}
}int main() {Test();return 0;
}