二元搜尋法(binary search)使用divide-and-conquer(分而治之)演算法技巧,對一個已排序(sorted)且長度為n的陣列A[0:n1],進行資料搜尋,其最差時間複雜度(worst case time complexity)可降到Θ (log n)。
(一) 請使用C或Java 語言,修改此二元搜尋法,使其能對未排序(unsorted)且長度為n的陣列A[0:n1],以divide-and-conquer 技巧,進行二元化搜尋。(15分)
(二) 請分析修改後的二元搜尋法其最差時間複雜度(worst case time complexity)以order Θ的方式表示。(5分)
(注意:不可將此陣列數值進行排序,請加註解說明程式碼作法)
題型:申論題
難易度:尚未記錄
2.
請使用C或Java語言寫一副程式void merge(int [] A, int [] B, int [] C, int n),此副程式將對兩個長度為n且已依小到大排序的整數陣列A與B,合併至長度為2n且依小到大排序的整數陣列C,此副程式的時間複雜度需為Θ(n)。(20分)
(注意:請加註解說明程式碼作法)