[問題] 請問取中間值所需的比較次數

[JFD (D)]

請問有沒有人知道取中間值所需的最少比較次數是多少次？

譬如
3個數字取中間值,最少需要三次
5個數字,最少需要六次
7個數字呢？

有理論公式可推到2n+1個嗎？

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.96.112.162
→ ken915007:2n+1...請看一下http://0rz.tw/Fky2Z 吧!
→ JFD:抱歉,我不知道這有什麼幫助,如果只是演算法,k-selection可以用
→ JFD:但這不是我要問的問題
※ 編輯: JFD             來自: 140.96.112.162       (12/22 16:51)
※ JFD:轉錄至看板 puzzle                                           12/22 16:56
推 FRAXIS:http://www.springerlink.com/content/f477q73800147349/
推 DJWS:http://eprints.kfupm.edu.sa/50355/1/50355.pdf
推 DJWS:我幫你google了一下，都沒看到有公式，只有看到bound而已。
→ JFD:very thanks
→ Lucemia:(n-1)+(n-1)/2