之前在《換個(gè)角度看數(shù)據(jù)結(jié)構(gòu)，可以讓編程更高效》我們學(xué)習(xí)了兩種數(shù)據(jù)結(jié)構(gòu)，并明白了選擇合適的數(shù)據(jù)結(jié)構(gòu)將會(huì)顯著地提升代碼的性能。即使是像數(shù)組和集合這樣相似的兩種數(shù)據(jù)結(jié)構(gòu)，在高負(fù)荷的運(yùn)行環(huán)境下也會(huì)表現(xiàn)得天差地別。

而今天，你將會(huì)發(fā)現(xiàn)，就算數(shù)據(jù)結(jié)構(gòu)確定了，代碼的速度也還會(huì)受另一重要因素影響，那就是算法。

算法這個(gè)詞聽起來很深?yuàn)W，其實(shí)不然。它只是解決某個(gè)問題的一套流程。準(zhǔn)備一碗麥片的流程也可以說是一種算法，它包含以下4 步（對(duì)我來說是4 步吧）。

(1) 拿個(gè)碗。

(2) 把麥片倒進(jìn)碗里。

(3) 把牛奶倒進(jìn)碗里。

(4) 把勺子放到碗里。

在計(jì)算機(jī)的世界里，算法則是指某項(xiàng)操作的過程。之前我們研究了4 種主要操作，包括讀取、查找、插入和刪除。下面我們還是會(huì)經(jīng)常提到它們，而且一種操作可能會(huì)有不止一種做法。也就是說，一種操作會(huì)有多種算法的實(shí)現(xiàn)。

我們很快會(huì)看到不同的算法能使代碼變快或者變慢——高負(fù)載時(shí)甚至慢到停止工作。不過，現(xiàn)在我們先來認(rèn)識(shí)一種新的數(shù)據(jù)結(jié)構(gòu)：有序數(shù)組。它的查找算法就不止一種，我們將會(huì)學(xué)習(xí)如何選出正確的那種。

有序數(shù)組

有序數(shù)組跟之前討論的數(shù)組幾乎一樣，唯一區(qū)別就是有序數(shù)組要求其值總是保持有序（你猜對(duì)了）。即每次插入新值時(shí)，它會(huì)被插入到適當(dāng)?shù)奈恢?，使整個(gè)數(shù)組的值仍然按順序排列。常規(guī)的數(shù)組則并不考慮是否有序，直接把值加到末尾也沒問題。

以數(shù)組[3,17,80,202]為例。

假設(shè)這是個(gè)常規(guī)的數(shù)組，你準(zhǔn)備將75 插入，那就可以把它放到尾端，如下所示。

計(jì)算機(jī)只要1 步就能完成這種操作。

但如果這是一個(gè)有序數(shù)組，你就必須要找到一個(gè)適當(dāng)?shù)奈恢?，使插?5 之后整個(gè)數(shù)組依然有序。

做起來可不像說的那么簡(jiǎn)單。整個(gè)過程不可能一步完成，因?yàn)橛?jì)算機(jī)需要先找出那個(gè)適當(dāng)?shù)奈恢茫缓髮⑵浼耙院蟮闹涤乙苼眚v出空間給75。下面就來介紹分解的步驟。

先回顧一下原始的數(shù)組。

第1 步：檢查索引0 的值，看75 應(yīng)該在它的左邊還是右邊。

因?yàn)?5 大于3，所以75 應(yīng)該在它右邊的某個(gè)位置。而具體的位置，目前還是不能確定，于是，再檢查下一個(gè)格子。

第2 步：檢查下一格的值。

因?yàn)?5 大于17，所以繼續(xù)。

第3 步：檢查下一格的值。

這次是80，大于75。因?yàn)檫@是第一次遇到大于75 的值，可想而知，必須把75 放在80 的左側(cè)以使整個(gè)數(shù)組維持有序。但要在這里插入75，還得先將它的位置空出來。

第4 步：將最后一個(gè)值右移。

第5 步：將倒數(shù)第二個(gè)值右移。

第6 步：終于可以把75 插入到正確的位置上了。

可以看到，往有序數(shù)組中插入新值，需要先做一次查找以確定插入的位置。這是它跟常規(guī)數(shù)組的關(guān)鍵區(qū)別（在性能方面）之一。

雖然插入的性能比不上常規(guī)數(shù)組，但在查找方面，有序數(shù)組卻有著特殊優(yōu)勢(shì)。

查找有序數(shù)組

之前我們介紹了常規(guī)數(shù)組的查找方式：從左至右，逐個(gè)格子檢查，直至找到。這種方式稱為線性查找。

接下來看看有序數(shù)組的線性查找跟常規(guī)數(shù)組有何不同。

設(shè)一個(gè)常規(guī)數(shù)組[17,3,75,202,80]，如果想在里面查找22（其實(shí)并不存在），那你就得逐個(gè)元素去檢查，因?yàn)?2 可能在任何一個(gè)位置上。要想在到達(dá)末尾之前結(jié)束檢查，那么所找的值必須在末尾之前出現(xiàn)。

然而對(duì)于有序數(shù)組來說，即便它不包含要找的值，我們也可以提早停止查找。假設(shè)要在有序數(shù)組[3,17,75,80,202]里查找22，我們可以在查到75 的時(shí)候就結(jié)束，因?yàn)?2 不可能出現(xiàn)在75的右邊。

以下是用Ruby 語言實(shí)現(xiàn)的有序數(shù)組線性查找。

因此，有序數(shù)組的線性查找大多數(shù)情況下都會(huì)快于常規(guī)數(shù)組。除非要找的值是最后那個(gè)，或者比最后的值還大，那就只能一直查到最后了。

只看到這里的話，可能你還是不會(huì)覺得這兩種數(shù)組在性能上有什么巨大區(qū)別。

這是因?yàn)槲覀冞€沒釋放算法的潛能。這是接下來就要做的。

至今我們提到的查找有序數(shù)組的方法就只有線性查找。但其實(shí)，線性查找只不過是查找算法的其中一種而已。這種逐個(gè)格子檢查直至找到為止的過程，并不是查找的唯一途徑。

有序數(shù)組相比常規(guī)數(shù)組的一大優(yōu)勢(shì)就是它可以使用另一種查找算法。此種算法名為二分查找，它比線性查找要快得多。

二分查找

你小時(shí)候或許玩過這樣一種猜謎游戲（或者現(xiàn)在跟你的小孩玩過）：我心里想著一個(gè)1 到100之間的數(shù)字，在你猜出它之前，我會(huì)提示你的答案應(yīng)該大一點(diǎn)還是小一點(diǎn)。

你應(yīng)該憑直覺就知道這個(gè)游戲的策略。一開始你會(huì)先猜處于中間的50，而不是1。為什么？因?yàn)椴还芪医酉聛砀嬖V你更大或是更小，你都能排除掉一半的錯(cuò)誤答案！

如果你說50，然后我提示要再大一點(diǎn)，那么你應(yīng)該會(huì)選75，以排除掉剩余數(shù)字的一半。如果在75 之后我告訴你要小一點(diǎn)，你就會(huì)選62 或63。總之，一直都猜中間值，就能不斷地縮小一半的范圍。

下面來演示這個(gè)過程，但僅以1 到10 為例。

這就是二分查找的通俗描述。

有序數(shù)組相比常規(guī)數(shù)組的一大優(yōu)勢(shì)就是它除了可以用線性查找，還可以用二分查找。常規(guī)數(shù)組因?yàn)闊o序，所以不可能運(yùn)用二分查找。

為了看出它的實(shí)際效果，假設(shè)有一個(gè)包含9 個(gè)元素的有序數(shù)組。計(jì)算機(jī)不知道每個(gè)格子的值，如下圖所示。

然后，用二分查找來找出7，過程如下。

第1 步：檢查正中間的格子。因?yàn)閿?shù)組的長(zhǎng)度是已知的，將長(zhǎng)度除以2，我們就可以跳到確切的內(nèi)存地址上，然后檢查其值。

值為9，可推測(cè)出7 應(yīng)該在其左邊的某個(gè)格子里。而且，這下我們也排除了一半的格子，即9 右邊的那些（以及9 本身）。

第2 步：檢查9 左邊的那些格子的最中間那個(gè)。因?yàn)檫@里最中間有兩個(gè)，我們就隨便挑了左邊的。

它的值為4，那么7 就在它的右邊了。由此4 左邊的格子也就排除了。

第3 步：還剩兩個(gè)格子里可能有7。我們隨便挑個(gè)左邊的。

第4 步：就剩一個(gè)了。（如果還沒有，那就說明這個(gè)有序數(shù)組里真的沒有7。）

終于找到7 了，總共4 步。是的，這個(gè)有序數(shù)組要是用線性查找也會(huì)是4 步，但稍后你就會(huì)見識(shí)到二分查找的強(qiáng)大。

以下是二分查找的Ruby 實(shí)現(xiàn)。

def binary_search(array, value)# 首先，設(shè)定下界和上界，以限定所查之值可能出現(xiàn)的區(qū)域。# 在開始時(shí)，以數(shù)組的第一個(gè)元素為下界，以最后一個(gè)元素為上界lower_bound = 0upper_bound = array.length - 1# 循環(huán)檢查上界和下界之間的最中間的元素while lower_bound <= upper_bound do# 如此找出最中間的格子之索引#（無須擔(dān)心商是不是整數(shù)，因?yàn)镽uby 總是把兩個(gè)整數(shù)相除所得的小數(shù)部分去掉）midpoint = (upper_bound + lower_bound) / 2# 獲取該中間格子的值value_at_midpoint = array[midpoint]# 如果該值正是我們想查的，那就完事了。# 否則，看你是要往上找還是往下找，來調(diào)整下界或上界if value < value_at_midpointupper_bound = midpoint - 1elsif value > value_at_midpointlower_bound = midpoint + 1elsif value == value_at_midpointreturn midpointendend# 當(dāng)下界超越上界，便知數(shù)組里并沒有我們所要找的值return nilend

二分查找與線性查找

對(duì)于長(zhǎng)度太小的有序數(shù)組，二分查找并不比線性查找好多少。但我們來看看更大的數(shù)組。

對(duì)于擁有100 個(gè)值的數(shù)組來說，兩種查找需要的最多步數(shù)如下所示。

• 線性查找：100 步
• 二分查找：7 步

用線性查找的話，如果要找的值在最后一個(gè)格子，或者比最后一格的值還大，那么就得查遍每個(gè)格子。有100 個(gè)格子，就是100 步。

二分查找則會(huì)在每次猜測(cè)后排除掉一半的元素。100 個(gè)格子，在第一次猜測(cè)后，便排除了50 個(gè)。

再換個(gè)角度來看，你就會(huì)發(fā)現(xiàn)一個(gè)規(guī)律。

長(zhǎng)度為3 的有序數(shù)組，二分查找所需的最多步數(shù)是2。

若長(zhǎng)度翻倍，變成7（以奇數(shù)為例會(huì)方便選擇正中間的格子，于是我們把長(zhǎng)度翻倍后又增加了一個(gè)數(shù)），則最多步數(shù)會(huì)是3。

若再翻倍（并加1），變成15 個(gè)元素，那么最多步數(shù)會(huì)是4。

規(guī)律就是，每次有序數(shù)組長(zhǎng)度乘以2，二分查找所需的最多步數(shù)只會(huì)加1。

這真是出奇地高效。

相反，在3 個(gè)元素的數(shù)組上線性查找，最多要3 步，7 個(gè)元素就最多要7 步，100 個(gè)元素就最多要100 步，即元素有多少，最多步數(shù)就是多少。數(shù)組長(zhǎng)度翻倍，線性查找的最多步數(shù)就會(huì)翻倍，而二分查找則只是增加1 步。

這種規(guī)律可以用下圖來展示。

如果數(shù)組變得更大，比如說10 000 個(gè)元素，那么線性查找最多會(huì)有10 000 步，而二分查找最多只有14 步。再增大到1 000 000 個(gè)元素，則線性查找最多有1 000 000 步，二分查找最多只有20 步。

不過還要記住，有序數(shù)組并不是所有操作都比常規(guī)數(shù)組要快。如你所見，它的插入就相對(duì)要慢。衡量起來，雖然插入是慢了一些，但查找卻快了許多。還是那句話，你得根據(jù)應(yīng)用場(chǎng)景來判斷哪種更合適。

總結(jié)

關(guān)于算法的內(nèi)容暫時(shí)就是這些。很多時(shí)候，計(jì)算一樣?xùn)|西并不只有一種方法，換種算法可能會(huì)極大地影響程序的性能。

同時(shí)你還應(yīng)意識(shí)到，世界上并沒有哪種適用于所有場(chǎng)景的數(shù)據(jù)結(jié)構(gòu)或者算法。你不能因?yàn)橛行驍?shù)組能使用二分查找就永遠(yuǎn)只用有序數(shù)組。在經(jīng)常插入而很少查找的情況下，顯然插入迅速的常規(guī)數(shù)組會(huì)是更好的選擇。

之后，我們還將需要學(xué)習(xí)如何規(guī)范地描述數(shù)據(jù)結(jié)構(gòu)和算法的時(shí)間復(fù)雜度。有了這種通用的表達(dá)方式，就能更容易地觀察出哪種算法符合我們的實(shí)際需求。

可以結(jié)合下面這本書，繼續(xù)接下來的學(xué)習(xí)。本文內(nèi)容也來源于此。

這是本數(shù)據(jù)結(jié)構(gòu)與算法的入門指南，不局限于某種特定語言，沒有復(fù)雜的數(shù)學(xué)公式，用通俗易懂的方式針對(duì)編程初學(xué)者介紹數(shù)據(jù)結(jié)構(gòu)與算法的基本概念，培養(yǎng)編程邏輯。

它的主旨就是數(shù)據(jù)結(jié)構(gòu)與算法，具體內(nèi)容如下。

第1章和第2章，解釋數(shù)據(jù)結(jié)構(gòu)和算法是什么，并探索時(shí)間復(fù)雜度這一判斷算法效率的概念。此過程中還會(huì)經(jīng)常提及數(shù)組、集合和二分查找。

第3章，以老奶奶都聽得懂的方式去揭示大O記法的本質(zhì)。因?yàn)榇驩記法全書都會(huì)用到，所以對(duì)這一章的理解非常重要。

第4章、第5章和第6章，進(jìn)一步探索大O記法，并以實(shí)例來演示如何利用它來加快代碼運(yùn)行速度。這一路上，還會(huì)提到各種排序算法，包括冒泡排序、選擇排序和插入排序。

第7章和第8章會(huì)再探討幾種數(shù)據(jù)結(jié)構(gòu)，包括散列表、棧和隊(duì)列，展示它們對(duì)代碼速度和可讀性的影響，并學(xué)會(huì)用其解決實(shí)際問題。

第9章會(huì)介紹遞歸，計(jì)算機(jī)科學(xué)中的核心概念。作者對(duì)其進(jìn)行了分解，考察它在某些問題上的利用價(jià)值。第10章會(huì)運(yùn)用遞歸來實(shí)現(xiàn)一些飛快的算法，例如快速排序和快速選擇，提升讀者的算法開發(fā)能力。

第11章、第12章和第13章會(huì)探索基于結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)，包括鏈表、二叉樹和圖，并展示它們?cè)诟鞣N應(yīng)用中的完美表現(xiàn)。

最后一章，第14章，介紹空間復(fù)雜度。當(dāng)程序運(yùn)行環(huán)境的內(nèi)存空間不多，或處理的數(shù)據(jù)量很大時(shí)，理解空間復(fù)雜度便顯得特別重要。

——

【圖靈教育】

閱讀改變世界，閱讀塑造人生

讓我們站在巨人的肩膀上，解鎖更多IT技能！