費氏搜尋法(Fibonacci Search)

費氏搜尋法的概念

費氏數列(Fibonacci Sequence)

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, ...

#{{{
\begin{eqnarray}
F(1) &=& 0 \nonumber \\
F(2) &=& 1 \nonumber \\
F(n) &=& F(n - 1) + F(n - 2), \text{where } n \geq 3 \nonumber \\
\end{eqnarray}
}}}#

#{{{
\begin{eqnarray}
F(0) &=& 0 \nonumber \\
F(1) &=& 1 \nonumber \\
F(n) &=& F(n - 1) + F(n - 2), \text{where } n \geq 2 \nonumber \\
\end{eqnarray}
}}}#

費氏樹(Fibonacci Tree)與二元搜尋樹(BST, Binary Search Tree)

             5
/ \
/   \
/     \
/       \
/         \
4           3
/ \         / \
/   \       /   \
3     2     2     1
/ \   /     /
2   1 1     1
/
1

             5
/ \
/   \
/     \
/       \
/         \
3           2
/ \         / \
/   \       /   \
2     1     1     1
/ \   /     /
1   1 1     1
/
1

#{{{
S(n) = F(n + 2) - 1
}}}#

        7
/ \
/   \
/     \
/       \
3         9
/ \       / \
/   \     /   \
1     5   8     9
\   / \
2 4   6

             7
/ \
/   \
/     \
/       \
/         \
4          10
/ \         / \
/   \       /   \
2     6     9    11
/ \   /     /
1   3 5     8
/
0

(很多網站提供的費氏搜尋法的演算法和程式碼很古怪，不曉得在算什麼，應該要按照上述的方式來算才是有意義的。)

二元搜尋法的二元搜尋樹與時間複雜度

https://magiclen.org/binary-search/

           6
/ \
/   \
/     \
/       \
/         \
/           \
2             9
/ \           / \
/   \         /   \
/     \       /     \
0       4     7      11
\     / \     \     / \
1   3   5     8  10  12

費氏搜尋法的過程

索引    0   1   2   3   4   5   6   7   8

○  ◎  ●
0   1   1

○  ◎  ●
0   1   1
9 >= 1

○  ◎  ●
0   1   1   2(1 + 1)

○  ◎  ●
0   1   1   2
9 >= 2

○  ◎  ●
0   1   1   2   3(1 + 2)

○  ◎  ●
0   1   1   2   3
9 >= 3

○  ◎  ●
0   1   1   2   3   5(2 + 3)

○  ◎  ●
0   1   1   2   3   5
9 >= 5

○  ◎  ●
0   1   1   2   3   5   8(3 + 5)

○  ◎  ●
0   1   1   2   3   5   8
9 >= 8

○  ◎   ●
0   1   1   2   3   5   8   13(5 + 8)

○  ◎   ●
0   1   1   2   3   5   8   13
9 < 13

○  ◎   ●
0   1   1   2   3   5   8   13

             <   <  ○  ◎   ●
0   1   1   2   3   5   8   13

○  ◎  ●
0   1   1   2   3   5   8   13

             7

○

79 > 69

     <   <  ○  ◎  ●
0   1   1   2   3   5   8   13

○  ◎  ●
0   1   1   2   3   5   8   13

             7
\
\
\
\
\
10

○

 <  ○  ◎  ●
0   1   1   2   3   5   8   13

○  ◎  ●
0   1   1   2   3   5   8   13

             7
\
\
\
\
\
10
/
/
9

○

○  ◎  ●
0   1   1   2   3   5   8   13

◎  ●
0   1   1   2   3   5   8   13

             7
\
\
\
\
\
10
/
/
9
/
8

○

79 == 79