高考申論題
110年
[資訊處理] 資料結構
第 一 題
📖 題組：
二元搜尋法（binary search）使用 divide-and-conquer（分而治之）演算法技巧，對一個已排序的（sorted）且長度為 n 的陣列 A[0:n-1]，以二元化方式進行資料值 x 的搜尋，其最差時間複雜度（worst case time complexity）可降到Θ(log n)。(一)請使用 C++或 Python 語言，修改此二元搜尋法，使其能對未排序的（unsorted）且長度為 n 的陣列 A[0:n-1]，進行三元化搜尋，即以 divide-and-conquer 技巧將此陣列切成三個子陣列，並在可能包含資料值 x 的子陣列繼續進行 divide-and-conquer 技巧的搜尋，如果找到則回傳 1，如果找不到則回傳 0。（17 分）（注意：請寫一個 searching 類別，內含一個 search 功能）(二)請分析修改後的三元化搜尋法其最差時間複雜度（worst case time complexity）以 order 的方式表示。（8 分）（注意：不可將此陣列數值進行排序，請加註解說明程式碼作法。）
二元搜尋法（binary search）使用 divide-and-conquer（分而治之）演算法技巧，對一個已排序的（sorted）且長度為 n 的陣列 A[0:n-1]，以二元化方式進行資料值 x 的搜尋，其最差時間複雜度（worst case time complexity）可降到Θ(log n)。(一)請使用 C++或 Python 語言，修改此二元搜尋法，使其能對未排序的（unsorted）且長度為 n 的陣列 A[0:n-1]，進行三元化搜尋，即以 divide-and-conquer 技巧將此陣列切成三個子陣列，並在可能包含資料值 x 的子陣列繼續進行 divide-and-conquer 技巧的搜尋，如果找到則回傳 1，如果找不到則回傳 0。（17 分）（注意：請寫一個 searching 類別，內含一個 search 功能）(二)請分析修改後的三元化搜尋法其最差時間複雜度（worst case time complexity）以 order 的方式表示。（8 分）（注意：不可將此陣列數值進行排序，請加註解說明程式碼作法。）
📝 此題為申論題，共 2 小題
小題 (一)
請使用 C++或 Python 語言，修改此二元搜尋法，使其能對未排序的（unsorted）且長度為 n 的陣列 A[0:n-1]，進行三元化搜尋，即以 divide-and-conquer 技巧將此陣列切成三個子陣列，並在可能包含資料值 x 的子陣列繼續進行 divide-and-conquer 技巧的搜尋，如果找到則回傳 1，如果找不到則回傳 0。（17 分）（注意：請寫一個 searching 類別，內含一個 search 功能）
思路引導 VIP
- 關鍵陷阱：題目強調「未排序（unsorted）」。2. 思考邏輯：在「已排序」的情況下，我們可以根據比較結果排除部分區間（剪枝）；但在「未排序」情況下，目標值 x 可能出現在任何一個子陣列中。因此，雖然使用了三元化的 divide-and-conquer 形式，但實際上必須搜尋所有三個子區間。3. 程式結構：建立一個
Searching類別，遞迴函數接收left與right指標，計算兩個切點m1,m2分成三段，分別遞迴呼叫。
小題 (二)
請分析修改後的三元化搜尋法其最差時間複雜度（worst case time complexity）以 order 的方式表示。（8 分）（注意：不可將此陣列數值進行排序，請加註解說明程式碼作法。）
思路引導 VIP
- 遞迴關係式：設 $T(n)$ 為長度 $n$ 陣列的搜尋時間。2. 拆解過程：在每一層，我們將問題分成 3 個規模約為 $n/3$ 的子問題，且必須搜尋所有子問題。所以 $T(n) = 3T(n/3) + C$。3. 套用 Master Theorem 或遞迴樹分析：$a=3, b=3$。根據 Master Theorem 第一型，$n^{\log_3 3} = n^1$，故結果為 $O(n)$。