1. 順序查找介紹

1.1 定義

查找是指在指定數據組合中找出滿足條件的元素個體。順序查找是按照序列原有順序對數組進行遍歷比較查詢的基本查找算法。

順序查找是最基礎也是最簡單的查找算法，在需要進行查找時，這是我們的首選方法，只有數據較多，結構復雜，耗時較多需要優化時，我們才會考慮使用其他查找方法。

1.2 基本原理

對于任意一個序列以及一個給定的元素，從第一個序列元素開始，將給定元素與序列中元素依次比較，若某個元素與給定元素相同，則查找成功，否則，若將序列中的元素與給定元素全部比較完，依然無法匹配相同，則查找失敗。

比如，拿著一張照片從一個班上找出對應學生，那么長相就是判定值，我們需要一個個學生依次去比對，長相一致則找出了該學生，如果全班都看了一遍，還是沒找到，則尋人失敗。

1.3 時間復雜度與空間復雜度

順序查找平均查找長度為 (n + 1) / 2，時間復雜度為 O(n) 。

順序查找是對數列順序的比較，沒有額外的空間，所以空間復雜度為常數 O(1)。

1.4 優缺點

優點：算法簡單，對表中元素排列次序無要求，且對關鍵字的次序無要求，插入和刪除元素都非常方便。

缺點：時間復雜度較大，當數據規模較大時，效率較低。

2. 代碼實現

2.1 代碼設計

a. 輸入需要查找的元素key；

b. 從數組首元素（i=0）開始查找，如果array[i] = key，則查找成功返回i；

c. 否則i加1，繼續查找，如果找到數組末尾，依然沒找到，則查找失敗，返回-1。

2.2 代碼實現

#include<stdio.h>
#include<string.h>
int search(int array[],int n,int key)
{
    int i;

    for(i = 0; i<n; i++){
        if(array[i] == key)
            return i;   //查找成功
    }
    return -1;          //查找失敗
}
int main(void)
{
    int arr[7] = {62,8,35,22,90,58,6};
    int key,ret;
    printf("請輸入需要查找的數字:");
    scanf("%d",&key);
    ret = search(arr,sizeof(arr)/4,key);
    if(ret < 0)
        printf("查找失敗\n");
    else
        printf("該數字為數組第%d個元素\n",ret+1);
    return 0;
}

運行結果：

請輸入需要查找的數字:58

該數字為數組第6個元素