一、算法介绍
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; }
3.测试用例及结果
arr[]={2,5,4,8,9,7}
查找元素8：
查找元素7：
查找元素0：
