二分搜索算法：函數、收益、時間和空間複雜度

介紹

在任何計算系統中，搜索都是需要開發的最關鍵的功能之一。 搜索技術用於文件檢索、索引和許多其他應用程序。 有許多可用的搜索技術。 其中之一是二進制搜索技術。

二分搜索算法的工作原理是在每次迭代時忽略列表的一半。 它繼續拆分列表，直到在給定列表中找到它正在尋找的值。 二分搜索算法是對簡單線性搜索算法的快速升級。

無需編碼經驗。 360° 職業支持。 來自 IIIT-B 和 upGrad 的機器學習和人工智能 PG 文憑。

二分搜索算法的工作

首先要注意的是，二進制搜索算法總是在排序列表上工作。 因此，第一個合乎邏輯的步驟是對提供的列表進行排序。 排序後，將列表的中位數與所需值進行檢查。

• 如果期望值等於中心索引的值，則索引作為答案返回。

• 如果目標值低於列表的中心索引的交易，則忽略列表的右側。

• 如果期望值大於中心索引的值，則丟棄左半部分。

• 然後在短列表上重複該過程，直到找到目標值。

示例 #1

讓我們用一個例子來看看這個算法。 假設有一個包含以下數字的列表：

1、15、23、7、6、14、8、3、27

讓我們將所需的值設為 27。列表中的元素總數為 9。

第一步是對列表進行排序。 排序後，列表將如下所示：

1、3、6、7、8、14、15、23、27

由於列表中的元素數量為 9，因此中心索引為 5。 索引 5 處的值為 8。將所需的值 27 與值 8 進行比較。首先，檢查該值是否等於 8。 如果是，則返回索引並退出。

由於 27 大於 8，我們將忽略左側部分，只遍歷列表的右側。 要遍歷的新列表是：

14、15、23、27

注意：在實踐中，列表不會被截斷。 只是縮小了觀察範圍。 因此，不應將“新列表”與製作新列表或縮短原始列表相混淆。 雖然它可以用一個新的列表來實現，但有兩個問題。 首先，會有內存開銷。 每個新列表都會增加空間複雜度。 其次，每次迭代都需要跟踪原始索引。

新的中心索引可以作為第二個或第三個元素，具體取決於實現。 在這裡，我們將把第三個元素視為中心。 將值 23 與值 27 進行比較。由於值大於中心值，我們將丟棄左半部分。

要遍歷的列表是：

27

由於列表僅包含一個元素，因此它被認為是中心元素。 因此，我們將期望值與 27 進行比較。當它們匹配時，我們返回原始列表中的索引值 27。

示例 #2

在同一個列表中，讓我們假設所需的值為 2。

首先，將中心值 8 與 2 進行比較。由於期望值小於中心值，我們將關注點縮小到列表的左側。

新的遍歷將包括：

1、3、6、7

讓我們將中心元素作為第二個元素。 將期望值 2 與 3 進行比較。由於值仍然較小，我們再次將焦點縮小到列表的左側。

新的遍歷將包括：

1

由於遍歷列表只有一個元素，因此該值直接與剩餘元素進行比較。 我們看到這些值不匹配。 因此，我們使用錯誤消息跳出循環：未找到值。

數據科學高級認證、250 多個招聘合作夥伴、300 多個學習小時、0% EMI

時間和空間複雜度

二分查找算法的時間複雜度為 O(log n)。 當中心索引直接匹配所需值時，最佳情況的時間複雜度將是 O(1)。 最壞的情況可能是列表兩端的值或不在列表中的值。

二分查找算法的空間複雜度取決於算法的實現。 有兩種實現方式：

1. 迭代法
2. 遞歸方法

兩種方法完全相同，但在實現上有兩個不同之處。 首先，遞歸方法中沒有循環。 其次，它不是將新值傳遞給循環的下一次迭代，而是將它們傳遞給下一次遞歸。 在迭代法中，可以通過循環條件來控制迭代次數，而在遞歸法中，以最大值和最小值作為邊界條件。

在迭代方法中，空間複雜度為 O(1)。 而在遞歸方法中，空間複雜度為 O(log n)。

好處

• 二分搜索算法是一種實現起來相當簡單的搜索算法。

• 這是對線性搜索的顯著改進，與一些更難實現的搜索算法相比，它的性能幾乎相同。

• 二進制搜索算法在每次迭代時將列表分成兩半，而不是按順序梳理列表。 在大型列表中，此方法非常有用。

結帳：決策樹分類：您需要知道的一切

結論

二分搜索算法是計算領域中廣泛使用的算法。 它是一種胖而準確的搜索算法，可以在大小數據集上都很好地工作。 二分搜索算法是一種簡單且可靠的算法來實現。 通過時間和空間分析，使用這種特殊技術的好處是顯而易見的。

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