斐波那契二分检索C语言代码
时间: 2023-07-09 11:24:20 浏览: 46
以下是斐波那契二分查找的 C 语言代码实现:
```c
#include <stdio.h>
// 生成斐波那契数列
void generate_fibonacci(int *fib, int n) {
fib[0] = 0;
fib[1] = 1;
for (int i = 2; i < n; i++) {
fib[i] = fib[i - 1] + fib[i - 2];
}
}
// 斐波那契二分查找
int fibonacci_search(int *arr, int n, int key) {
int fib[100]; // 假设最大长度为 100
generate_fibonacci(fib, 100);
int k = 0;
while (fib[k] < n) {
k++;
}
int lo = 0;
int hi = n - 1;
while (lo <= hi) {
int mid = lo + fib[k - 1] - 1;
if (arr[mid] < key) {
lo = mid + 1;
k -= 2;
} else if (arr[mid] > key) {
hi = mid - 1;
k -= 1;
} else {
return mid;
}
}
return -1; // 查找失败
}
int main() {
int arr[] = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
int n = sizeof(arr) / sizeof(arr[0]);
int key = 7;
int idx = fibonacci_search(arr, n, key);
if (idx != -1) {
printf("找到了,下标为 %d\n", idx);
} else {
printf("没找到!\n");
}
return 0;
}
```
在这个实现中,我们首先生成了一个最大长度为 100 的斐波那契数列。然后,我们找到最小的大于等于待查找序列长度的斐波那契数,并用它来划分序列。最后,我们在递归查找过程中根据待查找元素与中间元素的大小关系来决定继续在哪个子序列中查找。如果查找成功,则返回找到的元素在序列中的下标;否则,返回 -1。