JavaScript 中的線性搜索

簡介

在計算機科學的上下文中，搜索是在給定列表/數組中定位特定元素的過程。如果我們密切關注，我們可以找到無處不在的搜索算法。

考慮登錄網站的過程。根據數據庫中現有的鍵值對搜索輸入的電子郵件和密碼以驗證用戶。

在本文中，讓我們看一下搜索給定元素列表的最基本算法 - 線性搜索 .

理解線性搜索

線性搜索算法是一組指令，用於遍歷給定列表並檢查列表中的每個元素，直到找到我們正在尋找的任何元素。我們正在尋找的元素的技術術語是 - key .

該算法從最左邊（或起始）元素開始繼續搜索，直到找到所需元素或遍歷列表中的所有元素。

如果找到元素，我們將返回位置（或 index ) 的元素。如果我們要查找的元素在列表中不存在，我們一般返回-1 .

JavaScript 中線性搜索的實現

我們可以使用 for 遍歷給定的列表 環形。再來看看Linear Search的實現：

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

在這裡，我們將遍歷數組中的所有元素，並將每個元素與鍵進行比較。如果找到匹配項，則返回元素的索引。在我們的例子中，變量 i 跟踪我們在數組中的位置，如果找到匹配項，則返回 i 的當前值 .

如果該元素在我們的列表中不存在，linearSearch 函數不會返回任何 i 循環中的值。我們只是return -1 在循環之後顯示該函數沒有找到所需的元素。

全局線性搜索

在前面的實現中，我們在遇到我們要查找的元素的第一次出現後返回一個值 (key ）。但是如果我們想要給定元素的所有出現的索引呢？

這就是全局線性搜索的用武之地。它是線性搜索的一種變體，我們正在尋找給定元素的多次出現。

下面看一下全局線性搜索的實現：

function globalLinearSearch(arr, key){
    let results = []
    for(let i = 0; i < arr.length; i++){
        if(arr[i] === key){
            results.push(i)
        }
    }
    // If results array is empty, return -1
    if(!results){
        return -1
    }

    return results
}

在這種情況下，我們不是立即返回匹配元素的索引，而是將其存儲在一個數組中。最後，我們返回了索引數組。

線性搜索的效率

線性搜索是 brute-force 的經典示例 算法。這意味著該算法不使用任何邏輯來嘗試快速完成它應該做的事情，或者以某種方式減少它搜索 key 的元素範圍 .其他搜索算法旨在通過對列表/數組進行某種預處理來更有效地做到這一點，例如對其進行排序。

線性搜索的時間複雜度是O(n) , 其中 n 是我們正在搜索的列表中的元素數。這是因為我們在計算時間複雜度時總是考慮最壞的情況。在線性搜索（與大多數搜索算法一樣）的情況下，最壞的情況發生在元素不存在於列表中時。在這種情況下，我們需要遍歷所有 n 元素來確定該元素不存在。

結論

在本文中，我們看到了線性搜索背後的邏輯，然後利用這些知識，我們在 JavaScript 中實現了算法。我們還研究了線性搜索算法的時間複雜度。

到目前為止，它是 simples 搜索算法，它不使用任何邏輯來嘗試丟棄特定範圍進行搜索或專注於速度。