線性搜尋(Linear Search or Sequential Search)

介紹

是一種陣列搜尋的演算法，從頭依序開始查找目標，直到找到目標數

(圖片來自於Data Structure and Algorithms Linear Search)

虛擬碼

LINEAR-SEARCH(array, n):
    for i from 0 to array.length - 1:
        if (array[i] == n):
            return i
    return -1

複雜度

時間複雜度

最壞(查找位置剛好在最後一項):

$O(n)$

最好(查找位置在第一項):

$O(1)$

平均:

$O(N/2)$

空間複雜度

因需要一個計數器和一個遍歷數據結構的指針

$O(1)$

程式碼

function linearSearch(arr, n){
    for (let i = 0; i < arr.length; i++) {
        const element = arr[i];
        if(element == n){
            return i;
        }
    }
    return -1;
}

let arr = [8,7,9,10,5,56,78,98];

console.log(linearSearch(arr, 56)); // 5
console.log(linearSearch(arr, 99)); // -1