线性搜索被定义为一种顺序搜索算法，从一端开始，遍历列表中的每个元素，直到找到所需的元素，否则搜索将继续，直到数据集的末尾。
线性搜索算法
线性搜索算法如何工作？
在线性搜索算法中：
1、每个元素都被视为该键的潜在匹配项并进行相同检查。
2、如果找到任何元素等于该键，则搜索成功并返回该元素的索引。
3、如果没有找到与键相等的元素，则搜索结果为“未找到匹配项”。
例如：考虑数组arr[] = {10, 50, 30, 70, 80, 20, 90, 40}且key = 30
步骤1：从第一个元素（索引0）开始，将key与每个元素（arr[i]）进行比较。
将 key 与第一个元素 arr[0] 进行比较。由于不相等，迭代器将移动到下一个元素作为潜在的匹配项。
将 key 与 arr[0] 进行比较
将 key 与下一个元素 arr[1] 进行比较。由于不相等，迭代器将移动到下一个元素作为潜在的匹配项。
将 key 与 arr[1] 进行比较
步骤2：现在，当将arr[2]与key进行比较时，值匹配。因此，线性搜索算法将产生一条成功消息，并在找到 key 时返回元素的索引（此处为 2）。
将 key 与 arr[2] 进行比较
线性搜索算法的实现：
下面是线性搜索算法的实现：
// C code to linearly search x in arr[].
#include <stdio.h>
int search(int arr[], int N, int x)
{
for (int i = 0; i < N; i++)
if (arr[i] == x)
return i;
return -1;
}
// Driver code
int main(void)
{
int arr[] = { 2, 3, 4, 10, 40 };
int x = 10;
int N = sizeof(arr) / sizeof(arr[0]);
// Function call
int result = search(arr, N, x);
(result == -1)
? printf("Element is not present in array")
: printf("Element is present at index %d", result);
return 0;
}
输出
元素出现在索引 3 处
线性搜索的复杂度分析：
时间复杂度：
最佳情况：在最好的情况下，键可能出现在第一个索引处。所以最好的情况复杂度是 O(1)
最坏的情况：在最坏的情况下，键可能出现在最后一个索引处，即与列表中开始搜索的末尾相反的位置。因此，最坏情况的复杂度是 O(N)，其中 N 是列表的大小。
平均情况： O(N)
辅助空间： O(1)，因为除了迭代列表的变量之外，没有使用其他变量。
线性搜索的优点：
1、无论数组是否已排序，都可以使用线性搜索。它可以用于任何数据类型的数组。
2、不需要任何额外的内存。
3、它是一种非常适合小型数据集的算法。
线性搜索的缺点：
线性搜索的时间复杂度为 O(N)，这反过来又使得大型数据集的搜索速度变慢。
不适合大型阵列。
什么时候使用线性搜索？
1、当我们处理小数据集时。
2、当您搜索存储在连续内存中的数据集时。