線性搜尋演算法(C++)詳解

線性搜尋（Linear Search）是一個非常簡單的演算法，有時也稱為順序搜尋，它使用一個迴圈按順序遍歷一個陣列，從第一個元素開始，它將每個元素與正在搜尋的值進行比較，並在找到該值或遇到陣列末尾時停止。如果正在搜尋的值不在陣列中，則演算法將搜尋到陣列的末尾。

以下是執行線性搜尋的函數的虛擬碼：

Set found to false
Set position to -1
Set index to 0

While index < number of elements and found is false
    If list[index]is equal to search value
        found = true
        position = index
    End If
    Add 1 to index
End While
Return position

下面的函數 searchList 是一個 C++ 程式碼的範例，用於對一個整數陣列執行線性搜尋。陣列 list 最多具有 size 個元素，以下語句將搜尋它是否出現了儲存在 value 中的數位。如果找到該數位，則返回其陣列下標。否則，返回 -1，表示該值沒有出現在陣列中。

int searchList(const int list[], int size, int value)
{
    int index = 0; //用作搜尋陣列的下標
    int position = -1; //用於記錄搜尋值的位置
    bool found = false; //指示值是否找到的標記
    while (index < size && !found)
    {
        if (list [index] == value)    // 如果找到該值
        {
            found = true; // 設定標記
            position = index; //記錄值的下標
        }
        index++; //轉到下一個元素
    }
    return position; // 返回該位置或-1
}

注意，-1 被選作表示在陣列中找不到搜尋值的原因是：-1 不是有效的下標。其實，任何其他非有效的下標值也可以用來指示這一點。

下列程式是一個使用 searchList 函數的完整程式。它搜尋一個包含 5 個元素的 test 陣列，以查詢得分為 100 的專案。

// This program demonstrates the searchList function,which performs a linear search on an integer array.
#include <iostream>
using namespace std;
// Function prototype
int searchList(const int [], int, int);
const int SIZE = 5;
int main()
{
    int tests[SIZE] = {87, 75, 98, 100, 82};
    int results; // Holds the search results
    // Search the array for the value 100
    results = searchList(tests, SIZE, 100);
    //If searchList returned -1, 100 was not found
    if (results == -1)
        cout << "You did not earn 100 points on any test.n";
    else
    {
        // Otherwise results contains the subscript of the first 100 found in the array
        cout << "You earned 100 points on test ";
        cout << (results +1) << ".n";
    }
    return 0;
}
int searchList(const int list[], int size, int value)
{
    int index =0; // Used as a subscript to search array
    int position = -1; // Used to record position of search value
    bool found = false; // Flag to indicate if the value was found
    while (index < size && !found)
    {
        if (list[index] == value)// If the value is found
        {
            found = true; // Set the flag
            position = index; // Record the value's subscript
        }
        index++; // Go to the next element
    }
    return position; // Return the position, or -1
}

程式輸出結果：

You earned 100 points on test 4.

線性搜尋的效率缺陷

線性搜尋的優點是簡單，它很容易理解和實施。此外，它不要求陣列中的資料以任何特定順序儲存。

但是，它的缺點是效率低下。如果要搜尋的陣列包含 20 000 個元素，則演算法將不得不檢視所有 20 000 個元素，以便找到儲存在最後一個元素中的值或確定所需元素不在陣列中。

在一個典型的案例中，一個專案在陣列開頭附近的位置被發現和在末尾附近被發現的可能性是差不多的。平均而言，對於 N 個專案的陣列，線性搜尋將需要 N/2 次嘗試才能找到專案。如果一個陣列有 20 000 個元素，則線性搜尋平均需要對 10 000 個元素進行比較（N/2 是平均比較次數，最大比較次數總是 N）。當然，這是假定所搜尋的專案在陣列中必定存在的情況。

當線性搜尋未能找到某個專案時，必須對該陣列中的每個元素進行比較。隨著搜尋失敗次數的增加，平均比較次數也會增加。所以，如果速度很重要，那麼在可以避免的情況下，線性搜尋不應該用於大型陣列。