作者mqazz1 (無法顯示)
看板CSSE
標題[問題] 有點難的搜尋演算法..
時間Fri May 7 22:47:48 2010
assume the input is an array of n integers with the following property:
絕對值｜a[i] - a[i+1]｜≦1, for i = 1,...,n-1, and a[1]<a[n]
given an integer x where a[1]≦x≦a[n],
design an algorithm to find if this array contains this x,
and if so, output one of its location(index) in this array.
use less than O(n) comparison.
請問這題應該從哪個方面下手
會比較簡易呢?
謝謝
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.228.25.146
1F：推 LPH66:去思考題目的條件 |a[i]-a[i+1]|<=1 的意義 05/07 23:14
2F：→ LPH66:另外, 題目只要求你找出一個, 而不是所有的位置 05/07 23:15
3F：→ LPH66:這點也很重要 05/07 23:15
4F：→ LPH66:(不負責任猜測: 這題貌似是出自冼老師的名題百則...) 05/07 23:16