如何學(xué)習(xí)算法之二分查找（包含python代碼示例）

前言

我經(jīng)常聽到教計(jì)算機(jī)的老師說：“想要學(xué)好計(jì)算機(jī)，沖高薪，你英語可以不好，但 數(shù)學(xué)一定要好，因?yàn)橥嬗?jì)算機(jī)玩到最后玩的就是數(shù)學(xué)。”這時(shí)候恐怕有人會(huì)說：我從小就不喜歡數(shù)學(xué)，大學(xué)高數(shù)課都是睡過來的。確實(shí)，課堂上數(shù)學(xué)的各種符號(hào)和表達(dá)式讓人望而生畏。但學(xué)習(xí)算數(shù)也可以很有趣，就像玩一個(gè)有趣的游戲一樣。慢慢的你就會(huì)愛上算法，喜歡琢磨一個(gè)問題的多種解決方案，因此找到最快最簡(jiǎn)便的解決方法。

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

何為二分查找？

假設(shè)你要曾經(jīng)看過的書中查找一段內(nèi)容，你已不記得大概位置了，只能根據(jù)看到的內(nèi)容來推測(cè)，這個(gè)時(shí)候人們往往會(huì)從中間翻開書，然后根據(jù)翻到的內(nèi)容往前或往后翻找。
又假設(shè)你要你登錄一個(gè)網(wǎng)站，當(dāng)你輸完賬號(hào)和密碼點(diǎn)擊登陸時(shí)，網(wǎng)站必須核實(shí)你的賬號(hào)是否存在，因此去先去數(shù)據(jù)庫(kù)里查找你的賬號(hào)?？赡芩鼤?huì)從數(shù)據(jù)庫(kù)的第一個(gè)賬號(hào)開始往后一個(gè)個(gè)查找，但好的做法是從中間開始查找。
這是關(guān)于查找問題，而在上面提到的情境中都可使用二分查找算法來解決問題。

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

示例代碼

# 一個(gè)關(guān)于二次查找的示例，給一個(gè)列表和數(shù)字，輸出這個(gè)數(shù)
# 字在列表中的序號(hào)（從1開始）和猜測(cè)的次數(shù)。
def binary_search(list, item):
    low = 0  # 計(jì)算機(jī)中的的數(shù)字從0開始
    high = len(list)  # 列表的長(zhǎng)度是可被猜測(cè)的最大序號(hào)
    times = 1  # 猜測(cè)的次數(shù)

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

測(cè)試一下

# 創(chuàng)建一個(gè)列表和待猜測(cè)的數(shù)字傳遞給函數(shù)。
my_list = range(1, 101)
print(binary_search(my_list, 75))

顯示一共猜測(cè)了2次，這個(gè)數(shù)字是列表的第75個(gè)數(shù)字。

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

一個(gè)笑話

可能有人就想二分查找就這么簡(jiǎn)單嗎？大佬曾經(jīng)說過：思路很簡(jiǎn)單，細(xì)節(jié)是魔鬼。這里講一個(gè)笑話：

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

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

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

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

另一本叫做算法圖解：

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