斐波那契二分查找的代码C++
时间: 2024-09-22 07:04:29 浏览: 20
斐波那契搜索(Fibonacci Search),又称为黄金分割搜索,是一种优化过的二分查找算法,它利用斐波那契数列的特点进行搜索。这个算法通常用于大规模数据集,因为它减少了比较次数,尤其是在数组接近有序的情况下效率更高。
以下是一个简单的C++实现斐波那契搜索的基本思路:
```cpp
#include <iostream>
#include <vector>
// 斐波那契数列相关的函数
int fibonacci(int n) {
if (n <= 0)
return 0;
else if (n == 1)
return 1;
else
return fibonacci(n - 1) + fibonacci(n - 2);
}
// 查找目标值在排序数组中的位置
int fibonacciSearch(const std::vector<int>& arr, int target) {
// 获取两个足够大的斐波那契数
int fib_m_minus_2 = 0, fib_m_minus_1 = 1, fib_m = fibonacci(2);
while (fib_m < arr.size()) {
fib_m_minus_2 = fib_m_minus_1;
fib_m_minus_1 = fib_m;
fib_m = fibonacci_m_plus_1(fib_m);
// 计算搜索区间
int offset = fib_m_minus_1 > target ? fib_m_minus_1 : fib_m_minus_2;
int low = 0, high = arr.size() - fib_m;
// 调整边界并检查目标值
while (low <= high) {
int mid = low + ((high - low) >> 1); // 使用位运算避免溢出
if (arr[mid] == target)
return mid;
else if (arr[mid] < target)
low = mid + 1;
else
high = mid - 1;
}
}
// 如果未找到目标,返回-1
return -1;
}
int main() {
std::vector<int> arr = {1, 3, 5, 8, 13, 21, 34, 55};
int target = 21;
int result = fibonacciSearch(arr, target);
if (result != -1)
std::cout << "元素 " << target << " 在数组中的索引是 " << result << std::endl;
else
std::cout << "目标元素未找到" << std::endl;
return 0;
}
```