淺談資料結構與演算法 (2)– Array
這系列的文章將會試圖以一個非本科生的觀點，並用簡單易懂的方式講解一些在電腦科學領域中常見的資料結構以及相關的演算法。文章內容來自於我在臺大資工系的「資料結構與演算法」這門課中所學到的知識以及自己從不同來源所得到的內容，如對文章內容或是引用來源有疑問，歡迎在下方留言或是來信告知我～
This is the Chinese version. If you seek for the English version, please click the link below.
今天我們要來談的主題是 array，中文的名稱叫做陣列，在這篇文章中所講到的 array 都是指電腦科學中的 data structure。
What is an Array
我們先來看看維基百科對於 array 的說明。
a collection of same type data items that can be selected by indices computed at run-time
indices 是 index 的複數，而 index 指的是索引，基本上你可以想成編號。也就是說 array 其實就是一群性質相同的東西，而我們可以透過編號取得其中的某一個。
可以將 array 想像成置物櫃的空格，每個空格在外觀上都是一樣的，且每個空格都有一個編號，當我們把東西寄放在某個格子中時，只要記住自己放東西的格子編號，之後就可以馬上找到我們的東西。
Memory as an array
array 可以說是最基礎且最重要的 data structure，它構成了大部分其他 data structures 的基礎。為什麼呢？因為電腦的主記憶體 (main memory) 基本上就是一個龐大的 array，只是每一個格子內儲存的是 0 或 1（二進位）。
程式在執行時，必須將相關的資料放進主記憶體裡，然後 CPU 才能去主記憶體撈取資料進行運算（因為重點在講解 data structures，所以這部分計算機結構相關的內容就簡單帶過）。
而當程式需告任何變數時，OS (作業系統) 就會在主記憶體裡找到對應所需大小的空地來給這個程式用，OS 會跟程式說這個變數在主記憶體的格子編號，這麼一來，之後程式要用的時候，就可以馬上跳到該位置並拿出資料來。下面是個極度簡化之後的說明，詳細的過程並沒有這麼簡單，不過這系列文章主要是要帶大家認識資料結構，因此若對計算機結構跟作業系統有興趣的朋友可以自行研究。
程式：Hey，我需要兩個格子來存放某個資料，你可以給我嗎？
OS：好，你可以從編號為 112 的格子開始用
程式：好，謝謝 （接著把資料存進去）
Array 的特性
- fast access by index
當我們使用 array 時，通常變數會指到 array 第一格的編號，就像上面的例子。假設今天我們要十格，第一格的編號是 44，那麼我們要拿第五格的資料時就知道，會是編號 44+(5–1) = 48 這格。 - fixed size
array 在宣告時就必須註明大小，這是為什麼呢？這又得說回主記憶體。假設現在記憶體的使用情況是下面這張圖，紅色代表該格有放資料。
可以看出，現在連續的空間最大的是四格，如果要存放的 array 大小超過四格，是放不下的。你說：那不就分開就好了嗎？當然可以，不過這樣就沒有 “連續” 了，也就代表沒有辦法用 “起點 (start) + 位移(offset)” 這種方式去很快地得到 array 中任一格的資料。
common operations
接下來我們要來講幾個 array 常用到的操作。
- construct(length)
建立一個長度為 length 的 array。 - get(index)
要取得 array 中某格的資料，前面講過，因為可以透過 “起點 + 位移” 這種方式，所以能馬上就得到。 - update(index, value)
更新 array 中某格的資料，一樣是馬上能完成，只要找到該格，然後把裡面放的東西更改成新的 value 即可。 - remove(index)
如果只是單純要刪除資料，那麼只要找到該格然後把裡面的東西拿掉即可，但是這會造成一個問題，如果很多格變空了，array 就變成斷斷續續的，長度跟裡面存放的資料數目不一，隨著空格越來越多，會變得不好管理，而且造成很多的記憶體浪費，因此通常會在刪除之後把後面的格子依序往前遞補。 - insert(index, value)
那如果是要在 array 中的某格新加入一個東西怎麼辦？這必須要分成幾種情形討論。
1. 那格是空的：讚！只要找到那格，東西丟進去就結束了。
2. 那格有東西了：那就從那格開始把後面每格的東西都往後丟一格，然後再放進去。
3. 那格有東西了，而且 array 還滿了：要嘛丟掉某格中的東西，不然就要重新找個更大的 array，把所有東西搬過去。
如果是第一個情況倒還好，第二、第三種就不是那麼好了，如果 array 裡面有很多格怎麼辦？可以想像處理的時間會變長，這牽扯到所謂的「時間複雜度 (time complexity)」，我們之後會再深入討論，現在只要知道，insert 這個動作不像其他動作，不論 array 有多大，都能保證在很短的時間完成。
Ordered Array
接下來我們要來講 array 中的一種特殊情形，叫做 ordered array，也就是排序過後的 array。根據 array 中儲存的資料種類，可能有不同的排序方式，例如：如果 array 儲存某群人的身高，可以將它由小到大 / 由大到小排列；如果存的是名字，可能按照名字在字典中的順序排等等。
那為什麼需要把 array 排序過呢？因為這樣找東西才會快！就跟你查字典一樣，假設你要找 order 這個單字，翻開字典某一頁，發現該頁都是 H 開頭的單字，你就會知道說 O 比 H 來得後面，所以會往後翻不會再往前翻，但這有一個前提就是字典是按照 A-Z 的順序去排的，如果字典不是這樣排，而是毫無規則的隨意排放單字，那你就要一頁一頁去翻。
binary search
上面講的概念其實就是最經典的搜尋演算法：二元搜尋法 (binary search)，而要使用 binary search 的前提就是 array 必須是排序過的才行。
所謂的二元是指在每一次搜尋的過程中，我們都可以剔除掉一半的資料，只需要去找剩下的另一半。最經典的例子莫過於「終極密碼」這個遊戲了，一個人在心中默想一個 0~100 的數字，然後另一個人來猜，如果猜錯了，就必須要告知是猜得太大了還是太小了。假設答案是 79，若一開始猜 50 會得到「太小了」，因此 0~50 都被剔除了，我們只需要考慮剩下的 51 ~ 100；再接著猜 75，會得到「太小了」，於是 51 ~ 75 又會被剔除，以此類推。
每次我們都從剩下的資料找到最中間的那點，太大的話，就往小的那邊走；反之，太小就往大的那邊走，這樣的話每次都能剔除一半的資料。
假設資料有一萬筆，沒有排序的情況下，最多需要找一萬次才能找到要的資料；若是有排序並採用 binary search，最多只需要 14 次就可以找到，假使資料更多筆，那麼差距會更大，至於到底是怎樣的差距，我們一樣到「時間複雜度」的單元再進行說明。
Insert & Update
前面有講到普通 array 的 insert / update，然而 ordered array 比起來限制又更多了一點，假設要在 ordered array 中插入某一筆資料，只要那筆資料按照順序排不會是最後一個的話，那麼排在它後面的資料都要往後一格，它才能放進去對的地方 (e.g. 1, 2, 4, 7, 10, 14 是個從小排到大的 array，如果今天要把 3 也放進去，那麼 4, 7, 10, 14 都要往後放），這就回到前面講過的問題，隨著 array 越來越大，這個動作會越來越耗時，而且 array 滿了就沒辦法再存。
而 update 也變得不是只有找到該格並且更新資料這麼簡單，因為改了數值之後順序可能就不正確了，例如上面的例子中，如果把 10 改成 5 ，那 1, 2, 4, 7, 5, 14 顯然沒有從小排到大，這樣就要把 5 移到正確的位置（ 4 的後面）才行。
這篇文章簡單的講解了 array 這個最基礎的資料結構，下一篇文章會講解本篇文章提及的「時間複雜度」究竟是什麼東西。如果覺得我的文章不錯，歡迎給我一點掌聲，我將非常感謝！
