作者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