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