線性搜索與二分搜索：線性搜索和二分搜索之間的區別

介紹

編程語言中的連續內存分配提供了存儲多個數據點的靈活實現。 如果我們想要分離數據並將所有相似的數據合併到一個連續的數據結構（如數組、列表等）中，這可以在其高峰期使用。

連續內存分配在現實世界的應用程序中有許多實現，例如計算機中的操作系統、數據庫管理系統等。這種數據結構被認為是一種靈活的數據結構，因為向數組添加新數據點只需要一個時間單位，即； O(1)。

但是當我們想要查看特定條目或搜索特定條目時就會出現問題，因為所有現實世界的應用程序都依賴於數據訪問命令。 而且這個任務必須足夠快，才能滿足處理器和內存的速度。

根據我們為搜索元素所做的比較次數，可以劃分出各種搜索算法。

如果我們比較數組中的每個數據點來搜索一個元素，那麼它被認為是一個順序搜索。 但是如果我們通過跳過一些比較只比較幾個元素，那麼它被認為是一個區間搜索。 但是我們需要一個數組按排序順序（升序或降序）來對其執行區間搜索。

順序搜索的時間複雜度是線性的 O(n)，二分搜索（區間搜索的一個例子）的時間複雜度是 O(log n)。 此外，還有其他搜索算法，如指數搜索、跳躍搜索等。

但主要使用線性搜索和二分搜索，其中線性搜索用於隨機或未排序的數據，而二分搜索用於已排序和有序的數據。 散列是一種特殊的搜索算法，其中訪問數據點的時間複雜度為 O(1)。

我們先來了解一下線性搜索和二分搜索的算法，然後比較一下線性搜索和二分搜索的區別。

線性搜索

正如已經討論過的，線性搜索算法會比較數組中的每個元素，這是執行此操作的代碼。

讓我們看一下代碼。

我們已經聲明了一個 linear_search 函數，它需要一個數組，整數鍵作為參數。 現在我們需要遍歷所有元素並比較它是否與我們的搜索鍵匹配，所以我們編寫了一個循環遍歷數組的 for 循環，在其中有一個 if 循環來檢查該位置的數字是否匹配是否使用搜索鍵。 如果我們找到匹配項，我們將返回該位置。 如果數組中沒有這樣的元素，那麼我們將在函數末尾返回 -1。

請注意，如果我們有多次出現相同的數字，那麼我們將返回其第一次出現的位置。

來到 main 方法，我們已經聲明並初始化了一個整數數組。 然後我們正在初始化必須搜索的鍵。 這裡我們對數組和鍵進行硬編碼，但您可以將其更改為用戶輸入。 現在我們已經獲得了元素列表和要搜索的鍵，調用線性搜索方法並記錄返回的索引。 稍後我們將檢查返回值並打印索引是否存在鍵，否則打印鍵未找到。

二進制搜索

二進制搜索比線性搜索更優化，但必須對數組進行排序才能應用二進制搜索。 這是執行此操作的代碼。

讓我們看一下代碼。

我們已經聲明了一個 binary_search 方法，它需要一個排序的整數數組和一個整數鍵作為參數。 我們正在初始化變量低、高、中。 這裡低，高是指針，其中低將位於 0 索引處，而高將位於開始處的 n 索引處。 那麼二分查找是如何工作的呢？

首先，我們將計算低和高的中間值。 我們可以將 mid 計算為 (low+high)/2，但有時 high 可能是一個很大的數字，將 low 加到 high 可能會導致整數溢出。 因此，將 mid 計算為 low+(high-low)/2 將是一種最佳方式。

我們會將 mid 的元素與搜索鍵進行比較，如果找到匹配項，我們將返回索引。 否則我們將檢查中間元素是大於鍵還是小於鍵。 如果 mid 更大，那麼我們只需要檢查數組的前半部分，因為數組後半部分中的所有元素都大於鍵，所以我們將更新 high 為 mid-1。

同樣，如果 mid 小於 key，那麼我們需要在數組的後半部分進行搜索，因此將 low 更新為 mid+1。 請記住，二分搜索基於遞減和征服算法，因為我們在每次迭代中忽略了數組的一半。

回到我們的代碼，我們已經構建了 main 方法。 初始化一個排序數組和搜索鍵，調用二分搜索，並打印結果。

現在我們已經了解了線性搜索和二分搜索的算法，讓我們比較這兩種算法。

線性搜索與二分搜索

在職的

• 線性搜索遍歷所有元素並將它們與必須搜索的鍵進行比較。
• 二進制搜索明智地減少了必須搜索的數組的大小，並且每次都將鍵與中間元素進行比較。

數據結構

• 線性搜索對於數組、列表、鍊錶等所有數據結構都很靈活。
• 因為我們需要多向遍歷，所以不能對所有數據結構執行二分查找。 所以不能使用像單鍊錶這樣的數據結構。

先決條件

• 線性搜索可以對所有類型的數據進行，數據可以是隨機的或排序的，算法保持不變。 所以不需要做任何前期工作。
• 二進制搜索僅適用於已排序的數組。 因此對數組進行排序是該算法的先決條件。

用例

• 對於較小且隨機排序的數據集，通常首選線性搜索。
• 對於較大且已排序的數據集，二進制搜索是首選。

效力

• 在較大數據集的情況下，線性搜索效率較低。
• 在較大數據集的情況下，二分搜索更有效。

時間複雜度

• 在線性搜索中，最佳情況復雜度為 O(1)，其中元素在第一個索引處找到。 最壞情況的複雜度是 O(n)，其中元素在最後一個索引處找到或元素不存在於數組中。
• 在二分查找中，最佳情況復雜度為 O(1)，其中元素位於中間索引處。 最壞情況的複雜度為 O( log 2 n)。

試運行

假設我們有一個大小為 10,000 的數組。

• 在線性搜索中，最佳情況復雜度為 O(1)，最壞情況復雜度為 O(10000)。
• 在二分查找中，最佳情況復雜度為 O(1)，最壞情況復雜度為 O( log 2 10000)=O(13.287)。

結論

我們已經理解了在數組中訪問數據的重要性，理解了線性搜索和二分搜索的算法。 瀏覽了線性搜索和二分搜索的代碼。 比較了線性搜索和二分搜索的區別，做了一個大型例子的dry run。

現在您已經了解了線性搜索和二分搜索之間的區別，嘗試為大型 sied 數據集運行這兩種代碼並比較執行時間，開始探索不同的搜索算法，並嘗試實現它們！

如果您想了解數據科學，請查看 IIIT-B 和 upGrad 的數據科學 PG 文憑，該文憑專為在職專業人士而設，提供 10 多個案例研究和項目、實用的實踐研討會、與行業專家的指導、1-與行業導師面對面交流，400 多個小時的學習和頂級公司的工作協助。

從世界頂級大學在線學習數據科學課程。 獲得行政 PG 課程、高級證書課程或碩士課程，以加快您的職業生涯。