피보나치검색과 보간검색

레코드 20개

 1, 3, 5, 7, 10, 11, 12, 14, 23, 24, 25, 30, 33, 38, 45, 49, 55, 56, 66, 77

 이렇게 있을때

 피보나치 검색과 보간검색 하는법좀 알려주세여

--------------------------------------------------------------------------------------------------------

인덱스는 0부터 19까지라고 하겠습니다. 

==============================================================================

보간검색부터 보겠습니다.

최대값이 77이고 최소값이 1입니다. (77-1)/19를 해주면 76/19는 4로 딱 떨어지는 군요.

38을 찾아봅니다. 

(38-1)/4 를 해주면 9 가 나옵니다. 인덱스 9부터 선형으로 찾아갑니다.

24, 25, 30, 33, 38 이렇게 찾습니다.

12를 찾아봅니다.

(12-1)/4 는 2이니까 인덱스 2부터 시작합니다.

5, 7, 10, 11, 12 이렇게 찾아갑니다.

66을 찾아봅니다.

(66-1)/4는 16이니까 인덱스 16부터 시작합니다.

55, 56, 66 이렇게 찾아 갑니다.

만약 처음에 찾는수 보다 큰수를 만나면 뒤로 가면 되겠습니다.

보간검색은 분포가 일정할때 빨리 찾을수가 있습니다.

예를 들어서 

1, 5, 9, 13, 17, 21, 25, 29, 33, 37, 41, 45, 49, 53, 57, 61, 65, 69, 73, 77 과 같은

20개의 레코드가 있다면 한번만에 찾아 갈수가 있습니다.

----------------------------------------------------------------------------------

1, 3, 5, 7, 10, 11, 12, 14, 23, 24, 25, 30, 33, 38, 45, 49, 55, 56, 66, 77

피보나치 검색입니다. 

피보나치 수열을 이용합니다.

0 1 1 2 3 5 8 13 21   

k는 8입니다. fibo(8)=21이기 때문입니다.

38을 찾습니다. 

k는 8입니다 fibo(7)는 13입니다.

[2] 13번째 원소와 비교합니다. 

찾았습니다.

다음으로 12를 찾겠습니다.

 k는 8입니다. fibo(7)는 13입니다.

[2] 13번째 원소와 비교합니다. 

작습니다. 뒷부분은 버리고 앞에서 찾습니다. (k는 1이 줍니다)

k는 7이 됩니다. 그리고 fibo(6)=8 이기 때문에

[2] 8번째 원소와 12를 비교합니다.

작습니다. 뒷부분은 버리고 앞에서 찾습니다. (k는 1이 줍니다)

k는 6이 됩니다. 그리고 fibo(5)=5 이기 때문에

[2] 5번째 원소와 12를 비교합니다.

키값이 5번째 원소보다 큽니다. (이 때는 k가 2가 줄게 됩니다)

앞부분을 버리고 남아있는 원소를 가지고 피보나치 검색을 계속합니다.

이제부터는 6번째 원소가 1번째가 됩니다.

k는 4가 됩니다. 그리고 fibo(3)=2이기 때문에

[2] 2번째(실제는 7번째) 원소와 12를 비교합니다.

작습니다. 뒷부분은 버리고 앞에서 찾습니다. (k는 1이 줍니다)

k는 3이 됩니다. 그리고 fibo(2)=1 이기 때문에

[2] 1번째 원소(실제는 6번째) 와 12를 비교합니다.

찾았습니다.

다음으로 66을 찾겠습니다.

 k는 8입니다. fibo(7)는 13입니다.

[2] 13번째 원소와 비교합니다. 

큽니다.   (이때는 k가 2가 줄게 됩니다)

앞부분을 버리고 남아있는 원소를 가지고 피보나치 검색을 계속합니다.

이제부터는 14번째 원소가 1번째가 됩니다.

k는 6이 됩니다. 그리고 fibo(5)=5이기 때문에

[2] 5번째원소 (실제는 18번째) 와 비교합니다.

찾았습니다.

The Algorithm

Let Fk represent the k-th Fibonacci number 

where Fk+2=Fk+1 + Fk for k>=0 and F0 = 0, F1 = 1. 

To test whether an item is in a list of n = Fm ordered numbers, 

proceed as follows:

[0] Set k = m.

[1] If k = 0, finish - no match.

[2] Test item against entry in position Fk-1.

[3] If match, finish.

[4] If item is less than entry Fk-1, 

    discard entries from positions Fk-1 + 1 to n. 

    Set k = k - 1 and go to [1].

[5]  If item is greater than entry Fk-1, discard entries from positions 1 to Fk-1. 

    Renumber remaining entries from 1 to Fk-2, 

    set k = k - 2 and go to [1].