如何學習算法之二分查找（包含python代碼示例）

前言

我經常聽到教計算機的老師說：“想要學好計算機，沖高薪，你英語可以不好，但 數學一定要好，因為玩計算機玩到最后玩的就是數學。”這時候恐怕有人會說：我從小就不喜歡數學，大學高數課都是睡過來的。確實，課堂上數學的各種符號和表達式讓人望而生畏。但學習算數也可以很有趣，就像玩一個有趣的游戲一樣。慢慢的你就會愛上算法，喜歡琢磨一個問題的多種解決方案，因此找到最快最簡便的解決方法。

首先,什么是算法呢?算法是一系列解決任務的指令。任何一段代碼都可以稱為算法,但本文只展現算法的魅力,而不是大量的代碼,那樣也太乏味了。我們先從最簡單的二分查找開始。

何為二分查找？

假設你要曾經看過的書中查找一段內容，你已不記得大概位置了，只能根據看到的內容來推測，這個時候人們往往會從中間翻開書，然后根據翻到的內容往前或往后翻找。
又假設你要你登錄一個網站，當你輸完賬號和密碼點擊登陸時，網站必須核實你的賬號是否存在，因此去先去數據庫里查找你的賬號。可能它會從數據庫的第一個賬號開始往后一個個查找，但好的做法是從中間開始查找。
這是關于查找問題，而在上面提到的情境中都可使用二分查找算法來解決問題。

一個小游戲
假設我們來玩一個猜數字的游戲。你在紙上寫一個數字，范圍在1~100，然后找一個人來猜這個數字是多少。如果對方沒有猜中，你就告訴他，他猜的數字是大了還是小了，然后讓對方繼續猜，直到猜中這個數字為止。
問題是怎么猜才能用最少的次數來猜到這個數字呢？假設從1開始猜，而你寫的數字是100。對方先猜1，你說小了，對方繼續猜2，你還是告訴對方小了，對方又猜3……，直到你說99次小了，對方終于猜到了這個數字，但整整猜了100次，這實在是一種很槽糕的算法。
那如何更快的猜到數字呢？這次對方學聰明了，他不從頭開始猜，而是從中間開始猜。比如這次你還是寫了100，而對方猜的第一個數字是50，你說小了。對方又猜75，還是小了。對方又猜88（75和100之間的數字）……，當對方第七次猜的時候就能猜中這個數字。實際上無論你寫的數字是多少，對方總能在7次之內猜中這個數字，因為對方每次猜都能排除待選項中一半的數字。

示例代碼

# 一個關于二次查找的示例，給一個列表和數字，輸出這個數
# 字在列表中的序號（從1開始）和猜測的次數。
def binary_search(list, item):
    low = 0  # 計算機中的的數字從0開始
    high = len(list)  # 列表的長度是可被猜測的最大序號
    times = 1  # 猜測的次數

    # 只要范圍沒有縮小到只有一個元素，就檢查中間的元素
    while low <= high:
        # 將第一個數加上最后一個數除以二得出中間值，并取整。
        mid = int((low + high)/2)
        guess = list[mid - 1]
        # 如果猜測的數字等于給定的數字，則打印猜測的次數，并返回中間值
        if guess == item:
            print(times)
            return mid
        # 如果猜測的數字大于給定的數字則在中間值和最小值之間繼續尋找。
        if guess > item:
            high = mid - 1
            times = times + 1
        # 如果猜測的數字大于給定的數字則在中間值和最大值之間繼續尋找。
        else:
            low = mid + 1
            times = times + 1
    # 如果沒有這個數就返回None
    return None

測試一下

# 創建一個列表和待猜測的數字傳遞給函數。
my_list = range(1, 101)
print(binary_search(my_list, 75))

顯示一共猜測了2次，這個數字是列表的第75個數字。

可以看出二分查找擁有比簡單查找更快的運行時間，雖然簡單查找比二分查找的代碼更簡單不容易出bug，但所用的時間在大型項目中會造成很大的影響（比如有上千萬個數據時）。一個好的算法的判別條件有很多，比如時間代價，空間代價。但一定要有有窮性，確切性，可行性，和至少一個輸出。

一個笑話

可能有人就想二分查找就這么簡單嗎？大佬曾經說過：思路很簡單，細節是魔鬼。這里講一個笑話：

一天，小陳從圖書館出來，通過安檢門的時候警報響了，保安就讓他把書包里的N本書拿出來過一下，小陳剛準備一本本過的時候，保安露出鄙夷的目光說道：你難道不懂二分查找嗎？于是讓小陳把所有的書分成兩份后拿出一份過安檢，然后警報響了。然后在把那一份在分成兩份……。經過logN次后，保安找到了那本引起警報的書，露出得意和嘲諷的笑容。然后小陳拿著剩下的書走了。

從此，圖書館丟了N-1本書。

因此可見先要寫一個算法，需要考慮很多細節，并且要有很好的數學底子。在這里推薦兩本書，一本是普林斯頓微積分讀本

這本書對于，數學底子不好的人非常友善，從簡到難，循序漸進的進行教學，擁有大量通俗易懂說明讓你對基本的公式和原理有更好的理解。比起學校里的數學書更加讓人有興趣閱讀。

另一本叫做算法圖解：

這是一本非常有趣的算法書，能讓你像看漫畫一樣愉快的學習算法，其中的例子也鮮明有趣，其中還使用編程語言python的代碼作示例。可以讓你學習算法的同時，學習到一門當下最火的編程語言。