作者Hatred (yo)
看板CSSE
标题Re: [问题] 有点难的搜寻演算法..
时间Sat May 8 00:06:45 2010
※ 引述《mqazz1 (无法显示)》之铭言：
: 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.
: 请问这题应该从哪个方面下手
: 会比较简易呢?
: 谢谢
看起来像是 x 一定会出现, 找的方法应该可以这样吧:
令 m = n/2 的上高斯或下高斯, 然後问 a[m] 是不是 x, 如果是就搞定了, 否则若
a[m] > x, 就表示 a[1], ..., a[m-1] 里面有 x; 如果 a[m] < x, 就表示 a[m+1],
..., a[n] 里面有 x, 这样采用 binary search 继续做,就可以在 O(log n) 时间内
找出 x...
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 122.124.99.236
1F：推 mqazz1:不过想请问一下..这题 绝对值｜a[i] - a[i+1]｜≦1 05/08 11:24
2F：→ mqazz1:这个条件的意义大约是什麽? 05/08 11:24
3F：→ Hatred:就是在 i 逐步从 1 爬升到 n 的过程中, a[i] 的值不会一次 05/08 11:59
4F：→ Hatred:从小於 x 跳到大於 x 05/08 12:00
5F：→ LPH66:套冼老师在书上的说法就是「整数上的连续性」 05/08 15:30
6F：→ LPH66:只要想通了这就是连续 加上勘根定理的类比就容易得到这解法 05/08 15:31