暢銷書《算法圖解》推薦！文末留言贈書！

大家知道“猜數(shù)字”這個游戲嗎？顧名思義就是一個人想一個數(shù)字，另一個人猜。這個游戲簡單又有趣，小編小時候很喜歡玩。

游戲開始了！小伙伴從?1～100?中任選一個數(shù)字記在心里讓我猜，我每猜一個數(shù)字，他只能說小了、大了或?qū)α恕Ｖ钡轿也碌綌?shù)字，游戲結(jié)束。

那時的我比較笨，總是從 1 開始依次往上猜……

1，小了。那就是 2，2 也小。那就是 3……就這樣一個一個猜測數(shù)字花費(fèi)了很長時間。如果他定的數(shù)字是 99，那我要猜 99 次才能猜到！小伙伴表示很無奈，后來也不想再和我玩了。

長大之后的一次偶然的機(jī)會，我看到了一本書叫《算法圖解》。這本書上竟然提到了小時候我玩的“猜數(shù)字”游戲，我才了解到，這個游戲不是最終猜到這個數(shù)字就算贏，而是又快又準(zhǔn)確地猜到數(shù)字，那才是高手！那如何快速準(zhǔn)確地猜到數(shù)字呢？書中告訴了我們“猜數(shù)字”游戲快速勝出的小竅門，讓我大呼神奇，茅塞頓開。

首先從?50 開始猜。

小了，但我們可以排除一半的數(shù)字！1～50 都小了。接下來，猜 75。

大了，那余下的數(shù)字又排除了一半！75～100 都可以排除。接下來，猜 63（50 和 75 中間的數(shù)字）。

大了，但又可以排除一半數(shù)字！可以從 51～62 中選了！

接下來，猜 57（50 和 63 中間的數(shù)字）。對了！

書中說到，這種猜測方式其實(shí)就是算法的二分查找。沒想到小小的游戲也用到了算法。使用這種方法每次都能排除一半的數(shù)字。不管定數(shù)字的人心里想的是哪個數(shù)字，在 7 次之內(nèi)都能猜到。

而我小時候一個一個數(shù)字排除的那種方法其實(shí)也是一種方法，叫簡單查找，只不過這種方法比較笨。相比于簡單查找，二分查找大大節(jié)省了時間提高了效率。那么使用二分查找可節(jié)省多少時間呢？

簡單查找逐個地猜測數(shù)字，上面 100 個數(shù)字，最多需要猜 100 次。如果從 40 億個數(shù)字中猜呢？最多需要猜 40 億次。最多需要猜測的次數(shù)與列表長度相同，這被稱為線性時間（linear time）。

如果用二分查找的方式，二分查找的運(yùn)行時間為對數(shù)時間（或 log 時間）。100 個數(shù)字，最多要猜 7 次；40 億個數(shù)字，最多只需猜 32 次。厲害吧？看看是不是節(jié)省了很多時間呢？

后來我再玩這個游戲，使用了二分查找方法，總是能很快的猜對，所向披靡，屢戰(zhàn)屢勝。其實(shí)不光是在這個游戲中二分查找起到很大的作用，在日常的工作生活中，使用二分查找也同樣可以大大提高效率，節(jié)約時間，幫助我們解決問題。

比如，一個工人要維修一條 10km 長的電話線，想迅速查出故障所在。如果沿著線路一小段一小段查找，就很困難要花費(fèi)很長時間（簡單查找）。如果使用二分查找，把電線兩端設(shè)為 A、B，中點(diǎn)為 C，發(fā)現(xiàn) BC 段有故障，再找到?BC 中點(diǎn) D，發(fā)現(xiàn) CD 段有故障，再找到 CD 中點(diǎn) E……這樣每查一次，待查線路長度就縮減了一半，經(jīng)過 7 次查找，就可以找到故障發(fā)生的范圍了。

二分查找這么厲害，那下面我們再來看看如何編寫執(zhí)行二分查找的 Python 代碼吧！這里的代碼示例使用了數(shù)組。可將一系列元素存儲在一系列相鄰的桶（bucket），即數(shù)組中。這些桶從 0 開始編號：第一個桶的位置為 #0，第二個桶為 #1，第三個桶為 #2，以此類推。

函數(shù) binary_search 接受一個有序數(shù)組和一個元素。如果指定的元素包含在數(shù)組中，這個函數(shù)將返回其位置。我們將跟蹤要在其中查找的數(shù)組部分——開始時為整個數(shù)組。

我們每次都檢查中間的元素。

如果猜的數(shù)字小了，就相應(yīng)地修改 low。

如果猜的數(shù)字大了，就修改 high。完整的代碼如下。

你學(xué)會二分查找了嗎？那讓我們做一個小練習(xí)吧。假設(shè)有一個包含 128 個名字的有序列表，我們要使用二分查找在其中查找一個名字，請問最多需要幾步才能找到？（PS：評論區(qū)留言，第一個猜對的小伙伴，我們將有禮品相送~）

——以上內(nèi)容截選自《算法圖解》

有些算法學(xué)習(xí)者可能有過這樣的經(jīng)歷，學(xué)習(xí)算法初期看了幾本大塊頭的經(jīng)典算法巨著，但是看過就忘，對二分查找、大 O 表示法、遞歸、K 最近鄰算法等算法還是迷迷糊糊，不知所云。慢慢地就對算法失去了興趣，最終放棄。

算法巨著固然很好，但難度太大不適合剛?cè)腴T的小白，初期學(xué)習(xí)算法，還是培養(yǎng)興趣最為重要。如果算法書能像小說一樣有趣的話，相信很多人不會放棄算法了。

上面提到的《算法圖解》這本書就像小說一樣有趣。比如“猜數(shù)字”游戲，通過這個例子，大家可以輕松掌握理解二分查找的概念，算法也不再枯燥乏味難懂了。

書中一步步用圖的方式把算法解析出來，算法舉例簡單易懂，圖文并茂，公式極少。通過這本書算法初學(xué)者可以輕松理清算法基礎(chǔ)概念，潛移默化地培養(yǎng)算法思維，提升興趣，幫助大家步入算法殿堂。

下面是讀者朋友在豆瓣的真實(shí)評價：

作者：【美】巴爾加瓦（Aditya Bhargava）

譯者：袁國忠

本書特色

• 你一定能看懂的算法基礎(chǔ)書

• 代碼示例基于 Python

• 400 多個示意圖，生動介紹算法執(zhí)行過程

• 展示不同算法在性能方面的優(yōu)缺點(diǎn)

• 教會你用常見算法解決每天面臨的實(shí)際編程問題

你問我答

目錄

大佬推薦

本書完成了一項(xiàng)不可能完成的任務(wù)：讓數(shù)學(xué)變得有趣而易懂！?

——Sander Rossel，COAS Software Systems

你渴望像看喜歡的小說一樣學(xué)習(xí)算法嗎？如果是，本書正是你夢寐以求的！

——Sankar Ramanathan，IBM Analytics

當(dāng)今世界，使用算法進(jìn)行優(yōu)化已滲透到了生活的方方面面。如果你正尋找優(yōu)秀的算法入門書，本書就是你的首選。? ?

——Amit Lamba，Tech Overture

算法學(xué)習(xí)起來一點(diǎn)都不乏味！在我和學(xué)生們看來，本書既活潑有趣又富有洞見。

——Christopher Haupt，Mobirobo

作譯者介紹

作者

Aditya Bhargava

軟件工程師，兼具計算機(jī)科學(xué)和美術(shù)方面的教育背景，在 adit.io 撰寫編程方面的博客。

譯者

袁國忠

自由譯者；2000 年起專事翻譯，主譯圖書，偶譯新聞稿、軟文；出版譯著 40 余部，其中包括《Python編程：從入門到實(shí)踐》《C++ Prime Plus中文版》《CCNA學(xué)習(xí)指南》《CCNP ROUTE學(xué)習(xí)指南》《面向模式的軟件架構(gòu)：模式系統(tǒng)》《風(fēng)投的選擇：誰是下一個十億美元級公司》等，總計 700 余萬字；專事翻譯前，從事過三年化工產(chǎn)品分析和開發(fā)，做過兩年雜志和圖書編輯。

在文章底部留言，即可參加活動，留言獲贊最高前五名粉絲將贈一本！包郵到家！

截止時間：2月21日? ?20:00整

沒有抽中的粉絲不要?dú)怵H，打開下面鏈接，快快來搶購吧~

活動結(jié)束后，請讀者直接加我的微信領(lǐng)取獎品！

詳情點(diǎn)擊“閱讀原文”?