---
tags: 演算法, LeetCode
disqus: HackMD
---

# 線性搜尋(Linear Search or Sequential Search)

## 介紹

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

(圖片來自於[Data Structure and Algorithms Linear Search](https://www.tutorialspoint.com/data_structures_algorithms/linear_search_algorithm.htm))

## 虛擬碼

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