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