1.写出斐波那契二分检索,即使用斐波那契数列二分有序序列,查找某给定元素,找到返回下标,找不到返回-1
时间: 2024-03-16 10:47:41 浏览: 15
斐波那契二分检索是一种使用斐波那契数列进行二分查找的算法。它的基本思想是:将查找区间按照斐波那契数列进行分割,然后在分割出的小区间内进行二分查找。
下面是斐波那契二分检索的实现,其中fibonacci数组是斐波那契数列,n是要查找的元素个数,arr是一个已经排好序的数组,key是要查找的元素。
```c++
int fibonacciSearch(int arr[], int n, int key) {
int low = 0, high = n - 1;
int k = 0;
while (n > fibonacci[k] - 1) {
k++;
}
int* temp = new int[fibonacci[k] - 1];
for (int i = 0; i < n; i++) {
temp[i] = arr[i];
}
for (int i = n; i < fibonacci[k] - 1; i++) {
temp[i] = arr[n - 1];
}
while (low <= high) {
int mid = low + fibonacci[k - 1] - 1;
if (key < temp[mid]) {
high = mid - 1;
k = k - 1;
} else if (key > temp[mid]) {
low = mid + 1;
k = k - 2;
} else {
if (mid < n) {
return mid;
} else {
return n - 1;
}
}
}
return -1;
}
```
在这个算法中,我们首先需要计算出斐波那契数列中第k个数(满足fibonacci[k]-1>n)。然后我们将原数组arr复制到一个大小为fibonacci[k]-1的temp数组中,将temp数组中空出来的位置用最后一个元素填充。接下来,在temp数组上进行二分查找,如果找到了元素就返回它的下标,否则返回-1。
需要注意的是,这个算法需要使用动态内存分配来创建大小为fibonacci[k]-1的temp数组。另外,由于temp数组的大小可能比原数组arr的大小大,我们需要将temp数组中多余的部分用最后一个元素填充。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)