Re: [問題] 有點難的搜尋演算法..

[Hatred (yo)]

※ 引述《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
推 mqazz1:不過想請問一下..這題 絕對值｜a[i] - a[i+1]｜≦1
→ mqazz1:這個條件的意義大約是什麼?
→ Hatred:就是在 i 逐步從 1 爬升到 n 的過程中, a[i] 的值不會一次
→ Hatred:從小於 x 跳到大於 x
→ LPH66:套冼老師在書上的說法就是「整數上的連續性」
→ LPH66:只要想通了這就是連續  加上勘根定理的類比就容易得到這解法