99高考資料結構 - 高考

[考題] 國考歷屆考題與考題觀念討論(書裡看到的選這個)請附上想法、出處


出處:如題
假設有一個陣列A[0..12]，儲存13個數字：4，14，25，31，37，42，56，70，73，83，86，
90，94。今使用二元搜尋（binary search），問：
(一)寫出找尋70的比較過程（沒寫過程不予計分）。（8分）
(二)列出比較次數最多的所有數字。（6分）
(三)假設現有100,000個數字已經依由小而大的次序排列好，請分別使用二元搜尋（binary
search）與循序搜尋（sequential search），計算兩者成功找尋（successful search）
的平均比較次數，並說明兩者大概相差多少倍？（6分）


答：
(一)A[0..12]中間項56<70搜尋A[7..12]
A[7..12]中間項83>70搜尋A[7..8]
A[7..8] 中間項 70=70 搜尋成功。
(二)搜尋次數最的有：14,31,42,73,86,94




請問第(二)列出比較次數最多的所有數字
請問這是怎麼判斷的?

--