【演算】循序搜尋法 - Linear Search

　　循序搜尋法(linear search)屬於較簡易的搜尋演算法(search algorithm)，一般而言最常拿來介紹「搜尋」的概念。其執行原理如同其名，就是從第一個資料開始，依序尋找比對每一筆資料。

　　假設現在共有 n 筆資料，循序搜尋法的虛擬碼大致如下：

void linearsearch(Type data[1..n], Type search)
{
    Index i;

    for (i = 1 to n)
    {
        if (data[i] = search)
        {
            print i;
            return;
        }
    }

    print "Not found";
}

　　由於循序搜尋法會依序比對每一筆資料，所以其最大搜尋時間(最壞情況)為資料大小 n，就算是平均搜尋時間也有 n / 2。

　　我們可以發現到，循序搜尋法的搜尋時間會與資料量 n 成正比。所以這種搜尋演算法效率並不高，一般來說並不太實用。


　　以下是使用 C 語言的實作：

#include <stdio.h>
#include <stdlib.h>

int linearsearch(int[], int);

int n;

int main(void)
{
    int i, search, ans;
    int* data;

    printf("請輸入資料筆數: ");
    scanf("%d", &n);

    // 動態分配記憶體
    data = malloc(sizeof(int) * n);

    for (i = 0; i < n; i++)
    {
        printf("請輸入第 %d 筆資料: ", i + 1);
        scanf("%d", &data[i]);
    }

    printf("請輸入欲搜尋的資料: ");
    scanf("%d", &search);

    // 呼叫函式進行搜尋
    ans = linearsearch(data, search);

    if (ans < 0)
    {
        printf("找不到 %d\n", search);
    }
    else
    {
        printf("在第 %d 筆資料找到 %d\n", ans + 1, search);
    }

    // 釋放記憶體空間
    free(data);

    system("pause");
}

int linearsearch(int data[], int search)
{
    int i;

    for (i = 0; i < n; i++)
    {
        if (data[i] == search)
        {
            return i;
        }
    }

    return -1;
}