线性搜索算法(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）。当然，这是假定所搜索的项目在数组中必定存在的情况。

当线性搜索未能找到某个项目时，必须对该数组中的每个元素进行比较。随着搜索失败次数的增加，平均比较次数也会增加。所以，如果速度很重要，那么在可以避免的情况下，线性搜索不应该用于大型数组。