HeIp理解フィボナッチ検索

Question

インターネット上では私はアルゴリズムのコードしか見つけられませんが、コードのものだけを理解するのが難しいため、まずテキストの形で理解する必要があります。そしてアルゴリズムの他の記述は私にとっては非常に複雑です（Wikipediaや他のサイトで）。ここで

は、私がこれまでのために理解するものである：

レッツは、我々は、配列の要素10を検索したいと言う：

Index i 0 1 2 3 4 
     2 3 4 10 40 

ここではいくつかのフィボナッチ数：私たちは

Index j 0 1 2 3 4 5 6 7 8 9 
     0 1 1 2 3 5 8 13 21 34 

最初のもの配列の長さに等しいフィボナッチ数が見つかる。配列の長さは4なので、インデックス位置j=5にあるフィボナッチ番号5を取る必要があります。

ここで、私たちはここでアレイを分割し、どのように続行するのですか？私は実際にそれを理解していません..試験のために理解してください...

Answer 1

アルゴリズムは次のようになります： 配列の長さは5ですので、フィボナッチ数は5以上フィボナッチ数列に先行する2つの数は、2 [n-2]および3 [n-1] - （2,3,5）である。

したがって、ARR [N-2]、すなわちARR [2]要素は、その後、シーケンスは1時間にシフトされる数よりも小さい場合10.

である検索対象の数と比較されます左。また、インデックスのオフセットを与えるために、次の反復のために以前のインデックスが保存されます。この場合、4が小さいので、n-2は1（1,2,3）となる。したがって、数のインデックスは3です。

要素が大きい場合、シーケンスは2回左にシフトします。

常に、min（n-2 + offset、n）番目の要素とnumberを比較して、一致する結果を得ます。