作者mqazz1 (無法顯示)
站內Prob_Solve
標題[問題] unbounded search
時間Sat Dec 10 20:39:33 2011
Let A[n] be an array with n elements sorted in ascending order. It is simple
to construct an O(n lg n) algorithm to find the position k in A[n] for an
given value v. Assume that k is much less than n (i.e., v << n). Write an
O(lg k) time algorithm to search for k.
(Note: you do not know the value of k in advance, only v is known)
請問這題的題目在說甚麼呢?
input是v, 找k ? 這樣v跟k是甚麼關係?
又該怎麼解這題呢?
謝謝
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.118.110.186
1F：推 springman:k 是最後找到 v 的位置吧，a[k] = v，對嗎？ 12/11 03:16
2F：→ suhorng:可以請問題目原文在哪 ~? 12/11 11:09
原文
http://algnotes.wordpress.com/2010/05/31/binary-searchs-application/
※ 編輯: mqazz1 來自: 140.118.110.186 (12/11 19:31)
3F：推 DJWS:這個題目應該是有打錯字吧 12/11 20:05
4F：→ DJWS:我猜大意是這樣: 已排序陣列，長度為n，二分搜尋找值O(logn) 12/11 20:06
5F：→ DJWS:當n很大很大(數值v很小很小)(索引值k很小很小) 求O(logk)算法 12/11 20:08
6F：→ DJWS:方法是k從1開始，不斷放大兩倍，直到a[k]超過v。二分搜k/2~k 12/11 20:09