Learning

資料結構 - 二元搜尋

前情提要

這星期資結終於上機了，上週直接爽放一天假期ww
不過這周一上課就是混沌地獄，一堆人直接忘記 C 怎麼寫……（助教：完蛋了之後更難我豈不是忙死）
有人直接問怎麼輸入資料……連 scanf() 都忘記了嗎（尖叫
至於 VLA（int array[n]）跟 code 不排版就算了吧（點菸

慣例的廢話就到這邊，接著來聊聊這周的題目——二元搜尋法吧。

基本知識

一般我們在一串資料中要搜尋特定的一筆資料，直覺的方式就是從頭開始一筆筆比對，也就是所謂的線性搜尋，
但這樣需要花費的可能時間會非常的長，如果目標在最後一筆就會找非常久；
二元搜尋法則是利用「中間值」的概念，在一串已經排序過的資料中，每次都比對一定範圍的「中間」索引，
若不是目標資料的話則以中間值與其中一端為範圍，即縮小一半的搜尋區間，
然後不斷循環這樣的搜尋方式，直到找到目標。
這個方法相較於線性搜尋的好處是，搜尋的可能時間最壞會指數減少，
以演算法要求的時間複雜度而言，這是一個較好的解決方案。

題目

  • 輸入：輸入一個陣列長度，並依序輸入整數陣列資料，最後輸入一個搜尋目標。
  • 輸出：每一輪搜尋都輸出兩行，第一行為左右邊界及中間值的索引值，第二行為對應的資料；若最後有找到目標資料，輸出其索引值。
  • 注意：只能使用 C 或 C++，並請使用「遞迴」方式搜尋；另外本次的測資都是「可以找到目標」，不需要考慮找不到的情形。

實作

這邊就用我們的老朋友 C 來實作（C++？對不起我們不熟）。

注意 VLA

首先建立一個陣列，這邊許多初學者會犯的錯誤是 VLA（Variable Length Array，可變長度陣列），其實以安全性來說是非常不安全的。
什麼是 VLA？顧名思義，就是陣列的長度是可以更改的，如下列程式碼：

1
2
int n;          // 一堆人都用這個宣告大小我已經懶得吐嘈了
int array[n];   // 使用變數宣告陣列大小

你或許會問，長度可變不好嗎？陣列有彈性不是好事嗎？
但這樣宣告的問題在於，記憶體容易發生 stack overflow（不是我們常常抄 code 那個），
因為記憶體就是配置在一個固定大小的 stack，所以若是 n 太大就會爆掉。

如果真的需要陣列長度保持彈性，或者陣列大小依賴輸入值，
請務必使用動態記憶體分配的方式，如下：

1
2
3
4
#include <stdlib.h>     // 務必要寫這行，因為 malloc() 是定義在這個標頭檔裡面的

int size;
int *array = malloc(sizeof(int) * size);   // 動態宣告記憶體配置

上述宣告是基本使用 malloc() 的方式，但其實還可以修改成 int* array = malloc(sizeof *array * size)，
這樣若是陣列型態有變化，比較不會發生左邊改了但右邊忘記改的囧況。

二元搜尋算法

建立好陣列跟輸入資料，並且取得目標資料後，就是要考慮算法。

前面提到二元搜尋的方式是利用「區間中間值」，所以我們首先要考慮中間值的位置，
若陣列長度是奇數那就很簡單，但若是偶數，就需要定義中間值是哪一個，
一般我們會定義中間兩數取較小的為中間值：

1
int middle = (left + right) / 2;     // left 是左區間，right 是右區間

這邊不 - 1 是因為 C 的 / 運算在兩數皆為整數時只會取整數的商值，例如 9 / 2 得到的會是 4 而不是 4.5，
正好會符合前面所述取中間兩數較小者。

接著就是進行比對，如果一次就中當然幸運，直接回傳索引值；
但不是的時候肯定要進行下一輪比對，直到找到為止。
一般想法就是用迴圈跑，但這次題目要求用遞迴，那該怎麼寫？

使用遞迴

遞迴的寫法其實並沒有很複雜，比對過大小後，若不是目標就再次呼叫搜尋函式，不過會有兩種情形：

  1. 目標資料比中間資料大
  2. 目標資料比中間資料小

這兩種情形傳入函式的引數會不太一樣。

目標資料比中間資料大

代表目標資料索引在目前中間值的右邊，所以將中間值 + 1 作為新的左區間。

目標資料比中間資料小

代表目標資料索引在目前中間值的左邊，所以將中間值 - 1 作為新的右區間。

這邊用 switch-case 的方式判斷：

1
2
3
4
5
6
7
8
9
10
if (left <= right) {     // 因為資料排序過，應該是左區間小於右區間，若不是則整個函式回傳 -1
    switch (compare(array[middle], target)) {   // 比對目標與中間值，compare() 是另外宣告的比大小函式
        case -1:    // 目標比中間值大
            return search(array, target, middle + 1, right);
        case 0:     // 中間值即是目標
            return middle;
        case 1:     // 目標比中間值小
            return search(array, target, left, middle -1);
    }
}

最終結果

執行結果需要輸出每一次搜尋的左右區間跟中間值的「索引值」與「資料內容（數字）」，
因為每搜尋一次就要印一次，所以這個程序在每次呼叫搜尋函式就應該要被執行，故千萬不要寫在判斷式內，
而是輸出後再執行比對的判斷式；
最後找到目標資料後要將索引值單獨輸出一行，我自己的作法是將輸出的程序寫在主函式（int main()）裡面，
理由是我認為這個程序是在上述「搜尋」的函式以外的動作，所以我只讓搜尋函式在找到目標後回傳其索引給主函式，
而在主函式則設定一個變數接收最後回傳的索引值，並接著輸出：

1
2
int targetIndex = search(array, targer, 0, arraySize - 1);
printf("%d\n", targetIndex);

將以上組合就是這次的結果了。

結論與討論

這次終於不是我翻車了，但換來的是看到一堆令人吐血的慘烈 code（幹

其實二元搜尋真的沒有很難，這次我大約花半小時就完成，當然以高手的角度還是很慢了；
不過我主要是想檢討幾個能更好的地方：

1. 沒用指標

其實在 C 裡面善用指標能使執行效率有效提昇，因為電腦其實更認得記憶體位址而不是單純索引或是變數，
但我指標其實還需要補強（我因為指標被當過……），希望在學期結束前能更為熟練。

2. 沒有處理例外情況

雖然題目是說不會有找不到的情況，
但一個好的程式設計應該要設想到大部分的例外情況並處理，而不是放著讓程式噴 error；
搜尋函式其實在找不到的情況應該會回傳一個 -1，可以從這個地方切入去想想怎麼處理，
在看了許多高手的文章後，大部分會尋找一個近似值，之後我應該會找時間實作一下。

在每次的實作與錯誤（ㄈㄢ ㄔㄜ）中都能發現自己的不足並且檢討，
才能不斷進步，否則以後會繼續在同樣的地方跌倒。

最後預告一下，下一篇我可能不會寫技術實作，而是來聊聊所謂 coding style，
這次真的被某些同學嚇到了……