題組內容

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

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

詳解 (共 1 筆)

詳解 提供者：Yuan chen

計算總回合數：

  • 1 個 * 1 回合 = 1

  • 2 個 * 2 回合 = 4

  • 4 個 * 3 回合 = 12

  • 5 個 * 4 回合 = 20

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

37/12 = 3.08