斐波那契查找

Sally2121

请问下红色部分的代码有什么作用
mid什么情况下会大于high?不太明白这句话的意思

1. // ********************************
   
2. // By 小甲鱼，http://www.fishc.com
   
3. // ********************************
   
4. 
   
5. #include <stdio.h>
   
6. 
   
7. #define MAXSIZE 20
   
8. 
   
9. void fibonacci(int *f)
   
10. {
    
11.         int i;
    
12. 
    
13.         f[0] = 1;
    
14.         f[1] = 1;
    
15.        
    
16.         for(i=2; i < MAXSIZE; ++i)
    
17.         {
    
18.                 f[i] = f[i-2] + f[i-1];
    
19. 
    
20.         }
    
21. }
    
22. 
    
23. int fibonacci_search(int *a,int key,int n)
    
24. {
    
25.         int low = 0;
    
26.         int high = n - 1;
    
27.         int mid = 0;
    
28.         int k = 0;
    
29.         int F[MAXSIZE];
    
30.         int i;
    
31. 
    
32.         fibonacci(F);
    
33.        
    
34.         while( n > F[k]-1 )
    
35.         {
    
36.                 ++k;
    
37.         }
    
38. 
    
39.         for( i=n; i < F[k]-1; ++i)
    
40.         {
    
41.                 a[i] = a[high];
    
42.         }
    
43. 
    
44.         while( low <= high )
    
45.         {
    
46.                 mid = low + F[k-1] - 1;
    
47. 
    
48.                 if( a[mid] > key )
    
49.                 {
    
50.                         high = mid - 1;
    
51.                         k = k - 1;
    
52.                 }
    
53.                 else if( a[mid] < key )
    
54.                 {
    
55.                         low = mid + 1;
    
56.                         k = k - 2;
    
57.                 }
    
58.                 else
    
59.                 {
    
60.                         [color=Red]if( mid <= high )
    
61.                         {
    
62.                                 return mid;
    
63.                         }
    
64.                         else
    
65.                         {
    
66.                                 return high;
    
67.                         }
    
68.         [/color]        }
    
69.         }
    
70. 
    
71.         return -1;
    
72. }
    
73. 
    
74. 
    
75. 
    
76. int main()
    
77. {
    
78.        
    
79.         int a[MAXSIZE] = {1, 5, 15, 22, 25, 31, 39, 42, 47, 49, 59, 68, 88};
    
80.         int key;
    
81.         int pos;
    
82. 
    
83.         printf("请输入要查找的数字:");
    
84.         scanf("%d", &key);
    
85.        
    
86.         pos = fibonacci_search(a, key, 13);
    
87.        
    
88.         if( pos != -1 )
    
89.         {
    
90.                 printf("\n查找成功，可喜可贺，可口可乐! 关键字 %d 所在的位置是: %d\n\n", key, pos);
    
91.         }
    
92.         else
    
93.         {
    
94.                 printf("\nO~No~~小的办事不力，未在数组中找到元素:%d\n\n", key);
    
95.         }
    
96.                
    
97.         return 0;
    
98. }

复制代码

永恒的蓝色梦想

这不是叫二分查找？

Sally2121

斐波那契查找，0.618；
但我不太明白这个语句有什么作用

1. else
   
2.                 {
   
3.                         if( mid <= high )
   
4.                         {
   
5.                                 return mid;
   
6.                         }
   
7.                         else
   
8.                         {
   
9.                                 return high;
   
10.                         }
    
11.                 }

复制代码

python_ddd

Sally2121 发表于 2020-7-11 15:53
斐波那契查找，0.618；
但我不太明白这个语句有什么作用

因为前面考虑了可能会因斐波那契的F[k-1]和F[k-2]之和加起来大于数组a索引，所以会扩充a数组，但扩充的那部分实际上是不存在的，若迭代后mid指向了扩充的那部分，实际上那部分的值和a[high]是一样的，那时候返回索引high即可；

个人见解哈~