普考申論題
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]<x) r=m-1;
10 }
11 return -1;
12 }
13 }
三、關於搜尋法程式：
(一)說明循序（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]<x) r=m-1;
10 }
11 return -1;
12 }
13 }
📝 此題為申論題，共 2 小題
小題 (二)
以下二元搜尋程式碼有部分錯誤，若要修正為正確程式，請說明「最少」需修改程式碼行數、原因與修改方法。（17分）
(程式碼請參考大題題幹)
(程式碼請參考大題題幹)
思路引導 VIP
這是一題除錯（Debugging）題。檢視二元搜尋的核心迴圈中，當我們判斷中間值 arr[m] 與目標值 x 的大小關係時，邊界指標 l (left) 與 r (right) 該如何移動。
題目程式碼：
小題 (一)
說明循序（Sequential）搜尋法，以及二元（Binary）搜尋法的優缺點。（8分）
思路引導 VIP
這是一道標準的資料結構比較題。從「前置條件（是否需要排序）」、「時間複雜度（O(N) vs O(log N)）」、「適用的資料結構（Array vs Linked List）」三個維度來分別論述這兩種搜尋法的優缺點，條理會最清晰。