斐波那契查找是什么？黄金分割原理-js教程-PHP中文网

斐波那契查找是什么？黄金分割原理

月夜之吻

发布： 2025-08-13 14:36:02

原创

924人浏览过

斐波那契查找是一种利用斐波那契数列特性进行区间分割的高效查找算法，其核心是通过斐波那契数列确定分割点以逼近黄金分割比例，避免了二分查找中的除法运算，在某些硬件环境下能提升效率；该算法适用于静态有序数组，尤其在数组较大且频繁查找时优势明显，常用于嵌入式系统等对运算开销敏感的场景，最终若未找到目标则返回-1，整个过程以加减法和数列递推实现高效定位。

斐波那契查找是什么？黄金分割原理

斐波那契查找是一种利用斐波那契数列的特性来缩小查找范围的高效查找算法。它基于黄金分割比例，在某些情况下比二分查找更优。

斐波那契查找算法详解

斐波那契查找的核心在于利用斐波那契数列的特性来分割查找区间。首先，生成一个足够长的斐波那契数列，直到某一项大于等于待查找数组的长度。然后，利用斐波那契数列中的数值作为分割点的索引，逐步缩小查找范围。

具体步骤如下：

生成斐波那契数列： 生成一个斐波那契数列
```
F(k)
```
登录后复制
，使得
```
F(k) - 1
```
登录后复制
大于或等于待查找数组的长度
```
n
```
登录后复制
。
初始化： 设置
```
low = 0
```
登录后复制
，
```
high = n - 1
```
登录后复制
，
```
k
```
登录后复制
为满足
```
F(k) - 1 >= n
```
登录后复制
的最小索引。
循环查找：
- 计算分割点
```
mid = low + F(k-1) - 1
```
  登录后复制
  。
- 如果
```
key < arr[mid]
```
  登录后复制
  ，则
```
high = mid - 1
```
  登录后复制
  ，
```
k = k - 1
```
  登录后复制
  。
- 如果
```
key > arr[mid]
```
  登录后复制
  ，则
```
low = mid + 1
```
  登录后复制
  ，
```
k = k - 2
```
  登录后复制
  。
- 如果
```
key == arr[mid]
```
  登录后复制
  ，则返回
```
mid
```
  登录后复制
  。注意，如果
```
mid
```
  登录后复制
  超过了数组的实际长度，则返回
```
n - 1
```
  登录后复制
  。
未找到： 如果
```
low > high
```
登录后复制
，则表示查找失败，返回 -1。