斐波那契查找
请问下红色部分的代码有什么作用mid什么情况下会大于high?不太明白这句话的意思
// ********************************
// By 小甲鱼，http://www.fishc.com
// ********************************
#include <stdio.h>
#define MAXSIZE 20
void fibonacci(int *f)
{
int i;
f = 1;
f = 1;
for(i=2; i < MAXSIZE; ++i)
{
f = f + f;
}
}
int fibonacci_search(int *a,int key,int n)
{
int low = 0;
int high = n - 1;
int mid = 0;
int k = 0;
int F;
int i;
fibonacci(F);
while( n > F-1 )
{
++k;
}
for( i=n; i < F-1; ++i)
{
a = a;
}
while( low <= high )
{
mid = low + F - 1;
if( a > key )
{
high = mid - 1;
k = k - 1;
}
else if( a < key )
{
low = mid + 1;
k = k - 2;
}
else
{
if( mid <= high )
{
return mid;
}
else
{
return high;
}
}
}
return -1;
}
int main()
{
int a = {1, 5, 15, 22, 25, 31, 39, 42, 47, 49, 59, 68, 88};
int key;
int pos;
printf("请输入要查找的数字:");
scanf("%d", &key);
pos = fibonacci_search(a, key, 13);
if( pos != -1 )
{
printf("\n查找成功，可喜可贺，可口可乐! 关键字 %d 所在的位置是: %d\n\n", key, pos);
}
else
{
printf("\nO~No~~小的办事不力，未在数组中找到元素:%d\n\n", key);
}
return 0;
} 这不是叫二分查找？ 斐波那契查找，0.618；
但我不太明白这个语句有什么作用
else
{
if( mid <= high )
{
return mid;
}
else
{
return high;
}
} Sally2121 发表于 2020-7-11 15:53
斐波那契查找，0.618；
但我不太明白这个语句有什么作用
因为前面考虑了可能会因斐波那契的F和F之和加起来大于数组a索引，所以会扩充a数组，但扩充的那部分实际上是不存在的，若迭代后mid指向了扩充的那部分，实际上那部分的值和a是一样的，那时候返回索引high即可；
个人见解哈~
页:
[1]