搜索具有n個元素有序數(shù)組的某個元素時，最直接的方法就是對每個元素進行遍歷，也就是線性搜索，時間復雜度為O(n)。 還有一種更高效的搜索方法就是本文要介紹的二分查找，時間復雜度為O(logn)，本文介紹使用Python實現(xiàn)二分查找。

目錄

• 二分查找
• python實現(xiàn)二分查找
• 時間復雜度
• 總結

二分查找

二分查找要求查找數(shù)組是有序的，將有序的數(shù)組分成兩半， 如果搜索值小于中間位置記錄的值，則進一步查找前一個子表。 否則查找后一個子表。 重復上面的步驟，直到找到該值或不存在（間隔為0）。使用二分查找算法的前提：

查找數(shù)組是升序或者降序的

存在上下邊界

元素可以通過索引訪問

在升序排列數(shù)組：[2, 8, 10, 20, 30, 35, 42, 50, 52, 60] 中查找元素50.

python實現(xiàn)二分查找

下面使用Python實現(xiàn)二分查找

from typing import Listclass Solution:def binarySearch(self, arr: List[int], target:int):left, right = 0, len(arr) - 1while left <= right:mid = (left + right) // 2if arr[mid] == target:# find the target!! return midelif arr[mid] < target:left = mid + 1else: right = mid - 1 if __name__ == "__main__":Solu = Solution()result = Solu.binarySearch([2, 8, 10, 20, 30, 35, 42, 50, 52, 60],50)print(result)

執(zhí)行結果：

7

時間復雜度

在算法筆記：時間復雜度和空間復雜度中介紹了二分查找的時間復雜度一般使用主定理（The Master Theorem）來計算，時間復雜度可表示為：T(n) = T(n/2) + f(n)

下面推導一下二分查找時間復雜度的計算過程。

假設數(shù)組長度為n，且是有序的，迭代次數(shù)用k表示。

第一次迭代數(shù)組長度為n

第二次迭代數(shù)組長度為n/2

第三次迭代數(shù)組長度為(n/2)/2=n/(2^2)

第k次迭代數(shù)組長度為n/(2^k)=1

根據(jù)n/(2^k)=1可得n = 2^k

兩邊取對數(shù)：log2(n) = log2(2^k)
可得出：k = log2(n)

所以二分查找的時間復雜度為log2(n)

總結

本文介紹了對有序數(shù)組的二分查找算法，相對于線性搜索它的效率更高。對于搜索無序的數(shù)組，一種方法是先對它進行排序，然后用二分查找的方法，但排序的最優(yōu)復雜度也是O(nlogn)，使用線性搜索效率可能更高。還有一種提高無序數(shù)組搜索效率的解決方案是使用多線程的方法。

--THE END--

歡迎關注公眾號:「測試開發(fā)小記」及時接收最新技術文章！

總結

以上是生活随笔為你收集整理的常见搜索算法（二）：二分查找的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。