Re: [問題] 有點難的搜尋演算法..
※ 引述《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
推
05/08 11:24, , 1F
05/08 11:24, 1F
→
05/08 11:24, , 2F
05/08 11:24, 2F
→
05/08 11:59, , 3F
05/08 11:59, 3F
→
05/08 12:00, , 4F
05/08 12:00, 4F
→
05/08 15:30, , 5F
05/08 15:30, 5F
→
05/08 15:31, , 6F
05/08 15:31, 6F
討論串 (同標題文章)
CSSE 近期熱門文章
PTT數位生活區 即時熱門文章
