Python資料結構與算法（19）---二分查找

目錄

• 二分查找
• 圖解二分查找
• 實戰：二分查找

二分查找又名Binary Search，其采用折半的查找方式，實作對有序元素的快速查找。

相信看到上面二分查找的定義，讀者很容易就能想到，二分查找有一個非常重要的前提條件，那就是其需要已經排序好的數列。這樣，我們折半查找可以縮小查找的次數，更加的高效。

其具體原理：在數列中取中間下标值mid的元素e，進行查找元素key的比較。如果相等即查找成功，如果不等，大于就隻需要在後半部分查找，小于需要在前半部分查找。

不管是前半部分還是後半部分，我們在取其中間值mid，進行比較，依次類推，直到mid值等于key結束查找。

其時間複雜度為：O(log2n) 。

假設，我們現在有一個數列[1,3,5,7,9,11,13]，我們需要查找13所在的索引位置，那麼的步驟應該分幾步？

如上圖所示，我們這裡先取中間索引值3，與13進行比較。13不等于list[3]，且大于它，接下來我們需要取後半部分進行查找。

同樣的，在取後半部分中間值進行比較，依然大于它。最後，我們隻剩下一個值，如果相等，傳回查找到的索引，如果不等，傳回查詢不到。

了解其具體的原理之後，我們接下來通過Python來實作其二分查找的具體效果。示例代碼如下所示：

def binary_search(my_list, key):
    left = 0
    right = len(my_list)
    while left <= right:
        mid = (right - left) // 2
        if my_list[left + mid] < key:
            left = left + mid + 1
        elif my_list[left + mid] > key:
            right = left + mid - 1
        else:
            return left + mid
    return "None"


if __name__ == "__main__":
    my_list = [1, 3, 5, 7, 9, 11, 13]
    print("二分查找的原始數列：", my_list)
    print("二分查找的傳回結果：", binary_search(my_list, 3))