線性搜尋和二分搜尋的區別

在這篇文章中，我們將瞭解線性搜尋和二分搜尋的區別。

線性搜尋

  • 它從陣列/列表的開頭到結尾進行搜尋。

  • 陣列/列表中的每個元素都與需要搜尋的元素進行比較。

  • 它一直搜尋到列表的末尾。

  • 如果找到該元素，則返回一條包含索引的訊息。

  • 如果未找到該元素，則返回相關訊息。

  • 元素不需要以特定/排序的順序排列。

  • 它可以實現於任何線性資料結構，如陣列、連結串列。

  • 它基於順序方法。

  • 建議將其用於小型資料集。

  • 當陣列/列表的大小很大時，它的效率較低。

  • 查詢元素的最壞情況複雜度為 O(n)，其中‘n’是元素的數量。

  • 查詢元素的最佳情況複雜度為 O(1)。

  • 它可以用於一維和多維陣列。

二分搜尋

  • 要執行二分搜尋的陣列必須已排序。

  • 要搜尋的元素的位置是透過首先找到中間元素來確定的。

  • 中間元素是陣列/列表第一個索引和最後一個索引的平均值。

  • 它只能用於具有雙向遍歷的資料結構。

  • 它基於分治法。

  • 它用於大型資料集。

  • 它在大型資料集上效率更高。

  • 最壞情況複雜度為 O(log2n)，其中‘n’是陣列的大小。

  • 查詢元素的最佳情況複雜度為 O(1)。

  • 它只能在多維陣列上實現。

更新於: 2021年3月24日

3K+ 瀏覽量

開啟你的 職業生涯

透過完成課程獲得認證

開始學習
廣告