1. 順序查找介紹

1.1 定義

查找是指在指定數(shù)據(jù)組合中找出滿足條件的元素個(gè)體。順序查找是按照序列原有順序?qū)?shù)組進(jìn)行遍歷比較查詢的基本查找算法。

順序查找是最基礎(chǔ)也是最簡(jiǎn)單的查找算法，在需要進(jìn)行查找時(shí)，這是我們的首選方法，只有數(shù)據(jù)較多，結(jié)構(gòu)復(fù)雜，耗時(shí)較多需要優(yōu)化時(shí)，我們才會(huì)考慮使用其他查找方法。

1.2 基本原理

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

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

1.3 時(shí)間復(fù)雜度與空間復(fù)雜度

順序查找平均查找長(zhǎng)度為 (n + 1) / 2，時(shí)間復(fù)雜度為 O(n) 。

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

1.4 優(yōu)缺點(diǎn)

優(yōu)點(diǎn)：算法簡(jiǎn)單，對(duì)表中元素排列次序無要求，且對(duì)關(guān)鍵字的次序無要求，插入和刪除元素都非常方便。

缺點(diǎn)：時(shí)間復(fù)雜度較大，當(dāng)數(shù)據(jù)規(guī)模較大時(shí)，效率較低。

2. 代碼實(shí)現(xiàn)

2.1 代碼設(shè)計(jì)

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

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

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

2.2 代碼實(shí)現(xiàn)

#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("請(qǐng)輸入需要查找的數(shù)字:");
    scanf("%d",&key);
    ret = search(arr,sizeof(arr)/4,key);
    if(ret < 0)
        printf("查找失敗\n");
    else
        printf("該數(shù)字為數(shù)組第%d個(gè)元素\n",ret+1);
    return 0;
}

運(yùn)行結(jié)果：

請(qǐng)輸入需要查找的數(shù)字:58

該數(shù)字為數(shù)組第6個(gè)元素