題組內容

二、下圖是二元搜尋法（binary search）的一個示意圖。此例乃在一已排序 的陣列 A[0:11]中，找尋一個值為 Target=22 的元素的位置。一開始先 令 first←0，last←11。5c3d377e4dd4d.jpg

⑸此例如果陣列 A[0:11] 中 12 個元素每個元素被尋找的機率都一樣， 請問每個元素平均會用了幾個回合就找到了？（5 分）

詳解 (共 3 筆)

chris
chris
詳解 #3328531
2019/05/05
採用二分搜尋法之平均時間複雜度為O(lo...
(共 55 字，隱藏中）
前往觀看
馬
馬
詳解 #3244948
2019/03/14
38/12
(共 7 字，隱藏中）
前往觀看
Yuan chen
Yuan chen
詳解 #6983535
2025/10/28

計算總回合數：

  • 1 個 * 1 回合 = 1

  • 2 個 * 2 回合 = 4

  • 4 個 * 3 回合 = 12

  • 5 個 * 4 回合 = 20

總回合數 = 1 + 4 + 12 + 20 = 37 回合

37/12 = 3.08