線性搜尋
線性搜尋是最簡單的搜尋演算法。它也被稱為順序搜尋，因為在這種演算法中，我們通過遍歷整個陣列並將每個元素與所需的專案進行比較來尋找匹配的元素。如果找到了所需的元素，則返回索引或該元素；否則，我們繼續搜尋，直到用盡陣列。我們也可以在一個陣列中尋找一個專案的多次出現。它主要用於在一個未排序的陣列中搜尋專案。由於它比二叉搜尋慢得多，所以實際上並不使用。
線性搜尋演算法
假設我們有一個未排序的陣列 A[]，包含 n 個元素，我們想找到一個元素-X。
-
使用
for迴圈從最左邊的元素開始遍歷陣列中的所有元素，並執行以下操作。- 如果
A[i]的值與X相匹配，則返回索引i(如果可能有多個元素與X相匹配，則不返回索引i，而是列印所有索引或將所有索引儲存在一個陣列中並返回該陣列。) - 否則繼續下一個元素。
- 如果已在陣列的最後一個元素，退出
for迴圈。
- 如果
-
如果沒有一個元素匹配，則返回
-1。
線性搜尋示例
假設我們有陣列：(5, 3, 4, 2, 1, 6)。
- 情況 1：我們要尋找
X=5。
第一個元素本身是匹配的，我們返回索引 0。(最佳情況)
- 情況 2：我們想尋找
X=1。
我們遍歷陣列併到達索引 4，找到一個匹配的索引並返回該索引。(平均情況)
- 情況 3：我們要尋找
X=9。
我們遍歷陣列，但當我們到達陣列的最後一個元素時，沒有找到匹配的元素。我們返回 -1。(最壞情況)
線性搜尋演算法的實現
單一匹配的線性搜尋演算法
#include <iostream>
using namespace std;
int search(int arr[], int n, int x) {
// Traverse the array sequentially
for (int i = 0; i < n; i++) {
if (arr[i] == x) return i;
}
return -1;
}
int main() {
int n = 5;
int arr[] = {2, 4, 0, 1, 9};
int x = 1;
int result = search(arr, n, x);
if (result == -1)
cout << "Element not found";
else
cout << "Element found at index: " << result;
}
多重匹配的線性搜尋演算法
#include <bits/stdc++.h>
using namespace std;
vector<int> search(int arr[], int n, int x) {
vector<int> ans;
// Traverse the array sequentially
for (int i = 0; i < n; i++) {
if (arr[i] == x) {
ans.push_back(i);
}
}
return ans;
}
int main() {
int n = 9;
int arr[] = {2, 4, 0, 1, 9, 2, 1, 2, 1};
int x = 1;
vector<int> res = search(arr, n, x);
if (res.empty()) {
cout << "Element not found!!";
} else {
cout << "Element found at ";
for (int i = 0; i < res.size(); i++) {
cout << res[i] << " ";
}
}
}
線性搜尋演算法的複雜度
時間複雜度
- 平均情況
線性搜尋演算法的時間複雜度為 O(n)。
- 最佳情況
最佳情況下的時間複雜度是 O(1)。當要搜尋的元素是陣列中的第一個元素時，就會出現這種情況。
- 最壞情況
最壞的情況是，我們要搜尋的元素不在陣列內，或者在陣列的最後一個索引處。最壞情況下的時間複雜度是 O(n)。
空間複雜度
該演算法的空間複雜度取決於匹配的數量和使用的實現。一般來說，空間複雜度為 O(1)，但如果在一個陣列中儲存多個匹配索引，空間複雜度可能更高。
Harshit Jindal has done his Bachelors in Computer Science Engineering(2021) from DTU. He has always been a problem solver and now turned that into his profession. Currently working at M365 Cloud Security team(Torus) on Cloud Security Services and Datacenter Buildout Automation.
LinkedIn