普考申論題
112年
[資訊處理] 程式設計概要
第 一 題
📖 題組：
三、關於搜尋法程式： (一)說明循序（Sequential）搜尋法，以及二元（Binary）搜尋法的優缺點。（8分） (二)以下二元搜尋程式碼有部分錯誤，若要修正為正確程式，請說明「最少」需修改程式碼行數、原因與修改方法。（17分） 01 public class BinarySearch{ 02 public int faultyBinarySearch(int[] arr, int x){ 03 int l=0, r=arr.length-1; 04 int m=(l+r)/2; 05 while(l<=r){ 06 m=(l+r)/2; 07 if(arr[m]==x) return m; 08 if(arr[m]>x) l=m+1; 09 if(arr[m]
三、關於搜尋法程式： (一)說明循序（Sequential）搜尋法，以及二元（Binary）搜尋法的優缺點。（8分） (二)以下二元搜尋程式碼有部分錯誤，若要修正為正確程式，請說明「最少」需修改程式碼行數、原因與修改方法。（17分） 01 public class BinarySearch{ 02 public int faultyBinarySearch(int[] arr, int x){ 03 int l=0, r=arr.length-1; 04 int m=(l+r)/2; 05 while(l<=r){ 06 m=(l+r)/2; 07 if(arr[m]==x) return m; 08 if(arr[m]>x) l=m+1; 09 if(arr[m]
📝 此題為申論題，共 2 小題
小題 (一)
說明循序（Sequential）搜尋法，以及二元（Binary）搜尋法的優缺點。（8分）
思路引導 VIP
這是一道標準的資料結構比較題。從「前置條件（是否需要排序）」、「時間複雜度（O(N) vs O(log N)）」、「適用的資料結構（Array vs Linked List）」三個維度來分別論述這兩種搜尋法的優缺點，條理會最清晰。
小題 (二)
以下二元搜尋程式碼有部分錯誤，若要修正為正確程式，請說明「最少」需修改程式碼行數、原因與修改方法。（17分）
(程式碼請參考大題題幹)
(程式碼請參考大題題幹)
思路引導 VIP
這是一題除錯（Debugging）題。檢視二元搜尋的核心迴圈中，當我們判斷中間值 arr[m] 與目標值 x 的大小關係時，邊界指標 l (left) 與 r (right) 該如何移動。
題目程式碼：