經典算法之順序查找(Sequential Search)

目錄

• ​​順序查找​​

• ​​一、實作思路​​
• ​​二、代碼實作​​
• ​​三、算法分析​​

• ​​3.1 時間複雜度分析​​
• ​​3.2 空間複雜度分析​​
• ​​3.3 優缺點分析​​

• ​​寫在最後​​

順序查找

什麼是順序查找呢？順序查找是按照序列原有順序對數組進行周遊比較查詢的基本查找算法。簡單來說，就是給定一個數值，然後在給定的序列中按順序依次與給定值比較，若相等則查找成功，反之失敗！

一、實作思路

順序查找就是周遊給定的整個序列，逐個元素與給定值比較，若某個元素和給定值相等，則查找成功。如果直到最後一個元素和給定值比較都不相等，則查找失敗。

二、代碼實作

題目描述：給定一個整數數組 nums 和一個整數目标值 target ，請在數組中找到 target ，并傳回其下标。

public class SequentialSearch {
    public static void main(String[] args) {
        int[] nums = {12,15,54,85,25,64,54};
        Scanner sc = new Scanner(System.in);
        System.out.println("輸入要查找的資料：");
        int target = sc.nextInt();
        int i = search(nums, target);
        if(i != -1){
            System.out.println("查找成功，該元素的下标為" + i);
        }else{
            System.out.println("查找失敗！");

        }
    }

    /**
     * 順序查找
     * @param array
     * @param key
     * @return
     */
    static int search(int[] array,int key){
        for (int i = 0;i < array.length;i++){
            if (array[i] == key){
                return i;
            }
        }
        return -1;
    }
}      

三、算法分析

3.1 時間複雜度分析

使用順序查找在含有 n 個資料的序列中查找目标值，最理想的狀态是目标值位于序列第一位，隻需比較一次就找到目标值，此時的時間複雜度為O(1)；而最差的情況就是需要比較 n 次，也就是比較完序列中所有的資料，才找到目标值或者說不存在目标值，此時的時間複雜度為O(n)。

查找失敗時，需要比較 n + 1 次， 時間複雜度我們都會将結果去掉常數項，是以該算法的時間複雜度為O(n)。

3.2 空間複雜度分析

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

3.3 優缺點分析

優點：算法簡單，對表結構無任何要求，既适用于順序結構，也适用于鍊式結構。

寫在最後