[問題] unbounded search

[mqazz1 (無法顯示)]

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
推 springman:k 是最後找到 v 的位置吧，a[k] = v，對嗎？
→ suhorng:可以請問題目原文在哪 ~?
原文 http://algnotes.wordpress.com/2010/05/31/binary-searchs-application/

※ 編輯: mqazz1          來自: 140.118.110.186      (12/11 19:31)
推 DJWS:這個題目應該是有打錯字吧
→ DJWS:我猜大意是這樣: 已排序陣列，長度為n，二分搜尋找值O(logn)
→ DJWS:當n很大很大(數值v很小很小)(索引值k很小很小) 求O(logk)算法
→ DJWS:方法是k從1開始，不斷放大兩倍，直到a[k]超過v。二分搜k/2~k