高考申論題
113年
[資訊處理] 資料結構
第 一 題
📖 題組：
三、請使用虛擬碼（Pseudo Code）或任何程式語言，完成下列問題： (一)撰寫二元搜尋（Binary Search）的遞迴及非遞迴程式。（20 分） (二)推導二元搜尋的時間複雜度（Time Complexity）。（5 分）
三、請使用虛擬碼（Pseudo Code）或任何程式語言，完成下列問題： (一)撰寫二元搜尋（Binary Search）的遞迴及非遞迴程式。（20 分） (二)推導二元搜尋的時間複雜度（Time Complexity）。（5 分）
📝 此題為申論題，共 2 小題
小題 (一)
撰寫二元搜尋（Binary Search）的遞迴及非遞迴程式。（20 分）
思路引導 VIP
二元搜尋的前提是資料必須「已排序」。非遞迴版本（迭代）使用 while 迴圈與 low/high 指標；遞迴版本則需要將指標作為參數傳遞。注意邊界條件：low <= high 以及 mid 的計算方式，防止整數溢位（雖然在虛擬碼中通常寫 (low+high)/2 即可）。
小題 (二)
推導二元搜尋的時間複雜度（Time Complexity）。（5 分）
思路引導 VIP
二元搜尋每次將問題規模減半。建立遞迴式 $T(n) = T(n/2) + O(1)$。可以使用主定理 (Master Theorem) 或直接展開法。5 分的題目不需長篇大論，但推導邏輯要清晰。