資料結構與演算法
以二分搜尋在依升冪排列的陣列 a[0]～a[9] = 3, 8, 12, 17, 23, 31, 38, 45, 52, 60 中尋找38。搜尋範圍從下端 lo = 0、上端 hi = 9 開始，中央位置為 (lo + hi) ÷ 2 無條件捨去。依序排列與38比較的元素值，下列何者正確？
- A23, 38
- B31, 52, 45, 38
- C23, 45, 31, 38
查看答案與解析
正確答案：C. 23, 45, 31, 38
首先 (0 + 9) ÷ 2 = 4，與 a[4] = 23 比較，38較大，因此 lo = 5。接著 (5 + 9) ÷ 2 = 7，與 a[7] = 45 比較，38較小，因此 hi = 6。再來 (5 + 6) ÷ 2 = 5，與 a[5] = 31 比較後 lo = 6，最後在 a[6] = 38 相符。比較共4次，相當於元素數10時的最多次數 ⌊log₂ 10⌋ + 1 = 4。31、52、45、38 是中央位置採無條件進位時的順序，與題目的規則不同。
- A. 與23比較後，接著要與剩餘範圍 a[5]～a[9] 的中央 a[7] = 45 比較。
- B. 這是中央位置採無條件進位時的順序，與題目的規則不同。
- C. 正確。依序與 a[4]、a[7]、a[5]、a[6] 比較，第4次找到。