Python中如何實現二分查找

本篇文章為大家展示了Python中如何實現二分查找，內容簡明扼要并且容易理解，絕對能使你眼前一亮，通過這篇文章的詳細介紹希望你能有所收獲。

二分查找是一個用的非常多的查找算法，目的是從一個列表list里面，找到一個你想要的數，記做目標數據，返回這個數的索引，比如[5, 12, 3], 想找到12在哪，然后答案應該是1。直接的方法是從頭開始，一個個比較，如果相等就返回，先拿5和12比， 不相等就繼續下一個，12 = 12， 所以返回1，但是如果這個列表很大， 這樣查找起來就比較慢，時間復雜度是O（n），而二分查找是一個比較高效的查找方法，數學里面學過二分法，我覺得道理是類似的。二分查找的時間復雜度是O（logn）。

二分查找的一般過程為先找到數組的中間數據，然后對比目標數據和中間數據，如果相等則返回中間數據，如果目標數據大于中間數據，則繼續在列表的右邊按照相同方法去尋找。否則在左邊尋找；這里要注意的是，查找過程中的列表是經過排序以后的，所以這里比較的時候才會按大小去搜索。

下面是用Python實現二分查找的一個栗子

def binary_search(array, query_value):
    low, high = 0, len(array) - 1
    while low <= high:
        mid = low + (high - low) // 2
        mid_val = array[mid]
        if mid_val == query_value:
            return mid
        elif mid_val < query_value:
            low = mid + 1
        else:
            high = mid - 1
    return None


def main():
    array_1 = [1, 10, 20, 30, 180]
    print binary_search(array_1, 20)
    print "- * - " * 5
    array_2 = [2, 1, 3, 3, 5, 4, 1, 6]
    sorted_array = sorted(array_2)
    print "sorted_array : ", sorted_array
    print(binary_search(sorted_array, 5))


if __name__ == "__main__":
    main()

上述內容就是Python中如何實現二分查找，你們學到知識或技能了嗎？如果還想學到更多技能或者豐富自己的知識儲備，歡迎關注億速云行業資訊頻道。