[問題] unbounded search
看板Prob_Solve (計算數學 Problem Solving)作者mqazz1 (無法顯示)時間13年前 (2011/12/10 20:39)推噓2(2推 0噓 4→)留言6則, 3人參與討論串1/1
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
推
12/11 03:16, , 1F
12/11 03:16, 1F
→
12/11 11:09, , 2F
12/11 11:09, 2F
原文 http://algnotes.wordpress.com/2010/05/31/binary-searchs-application/
※ 編輯: mqazz1 來自: 140.118.110.186 (12/11 19:31)
推
12/11 20:05, , 3F
12/11 20:05, 3F
→
12/11 20:06, , 4F
12/11 20:06, 4F
→
12/11 20:08, , 5F
12/11 20:08, 5F
→
12/11 20:09, , 6F
12/11 20:09, 6F
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
