3.1.3 二分搜索的优缺点和适用场景

二分搜索的优点

• 二分搜索比线性搜索更快，尤其是对于大型数组。随着数组大小的增加，执行线性搜索所需的时间呈线性增加，而执行二分搜索所需的时间则呈对数增加。
• 二分搜索比具有类似时间复杂度的其他搜索算法（例如插值搜索或指数搜索）更有效。
• 二分搜索实现起来相对简单且易于理解，使其成为许多应用程序的不错选择。
• 二分搜索既可以用于排序数组，也可以用于排序链表，是一种灵活的算法。
• 二分搜索非常适合搜索存储在外部存储器（例如硬盘或云端）中的大型数据集。
• 二分搜索可以用作更复杂算法的构建块，例如计算机图形学和机器学习中使用的算法。

二分搜索的缺点

• 我们需要对数组进行排序。如果数组没有排序，我们必须先排序，然后再执行搜索。这为排序步骤增加了额外的 O(nlogn) 时间复杂度，这会使非常小的数组的二分搜索效率降低。
• 二分搜索要求被搜索的数组存储在连续的内存位置。如果数组太大而无法放入内存，或者如果数组存储在外部存储器（如硬盘驱动器）或云中，这可能会成为一个问题。
• 二分搜索要求数组的元素是可比较的，这意味着它们必须能够被排序。如果数组的元素不是自然排序的，或者如果排序没有明确定义，这可能是一个问题。
• 对于搜索无法放入内存的非常大的数据集，二分搜索的效率可能低于其他算法（例如哈希表）。

二分搜索的应用

• 机器学习中的搜索：二分搜索可以用作机器学习中使用的更复杂算法的构建块，例如用于训练神经网络的算法或寻找模型的最佳超参数的算法。
• 常用于竞争性编程。
• 可用于在计算机图形中搜索。二分搜索可以用作计算机图形学中使用的更复杂算法的构建块，例如光线跟踪或纹理映射算法。
• 可用于搜索数据库。二分搜索可用于有效地搜索记录数据库，例如客户数据库或产品目录。

何时使用二分搜索

• 在搜索大型数据集时，因为它具有 O(logn) 的时间复杂度，这意味着它比线性搜索快得多。
• 当数据集被排序时。
• 当数据存储在连续内存中时。
• 数据没有复杂的结构或关系。

3.1.4 推荐阅读

这里有几个可视化观察二分搜索过程的站点，可供学习：

• Binary Search animation
• Binary Search Animation by Y. Daniel Liang
• Binary and Linear Search Visualization
• Binary Search Tree Visualization

3.2 元二分搜索（单边二分搜索）

元二分搜索（Steven Skiena在《算法设计手册》中也称之为单边二分搜索）是二分搜索的一种改进形式，它以递增的方式构建数组中目标值的索引。与普通二分搜索一样，元二分搜索需要 O(lognlog{n}logn) 时间。

元二分搜索，也被称为单边二分搜索，是二分搜索算法的一种变体，用于搜索一个有序的列表或元素数组。这种算法是为了减少在列表中搜索一个给定元素所需的比较次数。

元二分搜索的基本思想是以一个大小为n的初始区间开始，其中包括整个数组。然后，该算法计算一个中间元素，就像二分搜索一样，并将其与目标元素进行比较。如果找到了目标元素，搜索就结束了。如果中间元素大于目标元素，算法将新的区间设置为上一个区间的左半部分，如果中间元素小于目标元素，新的区间被设置为上一个区间的右半部分。然而，与二分搜索不同，元二分搜索不对循环的每一次迭代进行比较。

该算法使用启发式方法来确定下一个区间的大小，它计算中间元素的值和目标元素的值之间的差异，并将该差异除以一个预先确定的常数，通常是2。该算法继续进行，直到找到目标元素或确定它不在列表中。

与二分搜索相比，元二分搜索的优点是在某些情况下可以进行较少的比较，特别是当目标元素接近列表的开头时。缺点是，在其他情况下，特别是当目标元素接近列表的末端时，该算法可能会比二分搜索执行更多的比较。因此，当列表的排序方式与目标元素的分布一致时，元二分搜索是最有效的。

JavaScript 实现：

function metaBinarySearch(arr, key) {
  const n = arr.length
  // 设置代表数组最大索引的比特数
  const lg = parseInt(Math.log(n - 1) / Math.log(2)) + 1
  // while ((1 << lg) < n - 1)
  // lg += 1;
  let pos = 0
  for (let i = lg; i >= 0; i--) {
    if (arr[pos] === key) return pos
    // 递增构建目标值的索引值
    const newPos = pos | (1 << i)
    // 在单边搜索并不断更新索引位置
    if (newPos < n && arr[newPos] <= key) pos = newPos
  }
  return arr[pos] === key ? pos : -1
}

Go 实现：

func metaBinarySearch(arr []int, key int) int {
    n := len(arr)
    lg := int(math.Log2(float64(n-1))) + 1
    pos := 0
    for i := lg; i >= 0; i-- {
        if arr[pos] == key {
            return pos
        }
        newPos := pos | (1 << i)
        if newPos < n && arr[newPos] <= key {
            pos = newPos
        }
    }
    if A[pos] == key {
        return pos
    } else {
        return -1
    }
}

时间复杂度：  O(lognlognlogn)，其中 n 是给定数组的大小

辅助空间：  O(1)，因为我们没有使用任何额外空间

4、三分搜索

考虑一个简单的例子，即双调序列：[1, 2, 3, 3, 3, 4, 4, 5, 5, 7, 6, 5, 5, 5, 4, 2, 2, 2]。

其中数字首先以递增顺序出现然后突然开始减少。现在，如果要求你在 O(logNlogNlogN) 的时间复杂度下找到最大数？你能用二分查找来解决这个问题吗？

实际上，除了二分搜索之外，其实还有三分搜索（Ternary Search）算法。它的知名度没有二分搜索那么高，但是用处也不小。一句话，三分搜索用来确定函数在凹/凸区间上的极值点。什么是凹凸性呢？借用同济版《高等数学（上册）》里的图来说明： 上图展示的是凹凸性的最简单情况。若函数 f(x) 在 区间I（曲线上任意两点x1、x2）上连续，恒有：

1. f((x1x_{1}x1 + x2x_{2}x2) / 2) < (f(x1x_{1}x1) + f(x2)) / 2，那么f(x)在区间I上是向上凹的；
2. f((x1x_{1}x1 + x2x_{2}x2) / 2) > (f(x1x_{1}x1) + f(x2)) / 2，那么f(x)在区间I上是向上凸的。

可见，凹凸性是相对的。有很多国外的书籍资料判断凹凸性时，是以原点方向为准，而不是y轴正方向，所以图a也可以是向下凸的，图b也可以是向下凹的。不管怎么说，函数f(x)在区间I上都有单峰（unimodal）性质，亦即有且仅有一个极值。三分搜索法就可以确定这个极值。

铺垫了这么多，三分搜索与二分搜索的本质不同是，在函数f(x)的某个区间[l, r]上取分界点时，不是只取一个中点，而是取两个分别位于1/3处的点，即：

m1 = l + (r - l) / 3，m2 = r - (r - l) / 3

这两个点把区间分成了三段。以凸函数（即有最大值）为例，有三种情况需要考虑：

• 若f(m1) < f(m2)，说明极值点位于[m1, r]区间内，可以不必再考虑[l, m1]区间；
• 若f(m1) > f(m2)，说明极值点位于[l, m2]区间内，可以不必再考虑[m2, r]区间。
• 若f(m1) = f(m2)，说明极值点位于[m1, m2]区间内。

这样，每一轮迭代都会把搜索范围限制在原来的2/3，直到最终逼近极值点，即l和r之间的差值接近无穷小。容易推导出三分搜索的时间复杂度为：

T(n) = T(2n / 3) + 1 = O(log3nlog_{3}nlog3n)

通过三分搜索算法，最大限度地提高你的搜索能力，减少时间的复杂性，实现更加高效的搜索。

三分搜索可以用来寻找数组中的一个元素。它类似于二分搜索，我们将数组分为两部分，但在这种算法中，我们将给定的数组分为三部分，并确定其中的关键（搜索的元素）。我们可以通过采取mid1和mid2将数组分成三部分，其计算方法如下所示。最初，l和r将分别等于0和n-1，其中n是数组的长度。这与二分搜索相同。唯一的区别是，它将时间复杂度降低了一些。它的时间复杂度是 O(log3nlog_3nlog3n)，二分搜索的时间复杂度是 O(log2nlog_2nlog2n)。

一般来说：

• 二分查找用于查找排序列表中的特定元素。
• 三元搜索用于查找函数的最大值或最小值。

注意： 数组需要排序才能对其进行三元搜索。

三元搜索的步骤：

1. 首先，我们将键与 mid1 处的元素进行比较。如果发现相等，我们返回 mid1。
2. 如果不是，则我们将键与 mid2 处的元素进行比较。如果发现相等，我们返回 mid2。
3. 如果不是，那么我们检查键是否小于 mid1 处的元素。如果是，则返回第一部分。
4. 如果不是，那么我们检查键是否大于 mid2 处的元素。如果是，则返回第三部分。
5. 如果不是，那么我们回到第二（中间）部分。

例子：

JavaScript 实现：

function ternarySearch(l, r, key, ar) {
  if (r >= l) {
    const mid1 = l + parseInt((r - l) / 3, 10)
    const mid2 = r - parseInt((r - l) / 3, 10)
    if (ar[mid1] == key) {
      return mid1
    }
    if (ar[mid2] == key) {
      return mid2
    }
    // 由于key不存在于中间，检查它存在于哪个区域，然后在该区域重复搜索操作
    if (key < ar[mid1]) {
      // key 在 l 和 mid1 中间
      return ternarySearch(l, mid1 - 1, key, ar)
    }
    if (key > ar[mid2]) {
      // key 在 mid2 和 r 中间
      return ternarySearch(mid2 + 1, r, key, ar)
    }
    // key 在 mid1 和 mid2 中间
    return ternarySearch(mid1 + 1, mid2 - 1, key, ar)
  }
  return -1
}

• 时间复杂度： O(���3�log3n)
• 辅助空间： O(���3�log3n)

Go 实现：

func TenarySearch(arr []int, left int, right int, target int) int {
    if left > right {
        return -1
    }
    partition := (right - left) / 3
    middle1 := left + partition
    middle2 := right - partition
    if arr[middle1] == target {
        return middle1
    } else if arr[middle2] == target {
        return middle2
    } else if target < arr[middle1] {
        return TenarySearch(arr, left, middle1-1, target)
    } else if target > arr[middle2] {
        return TenarySearch(arr, middle2+1, right, target)
    } else {
        return TenarySearch(arr, middle1+1, middle2-1, target)
    }
}

5、跳跃搜索

跳跃搜索算法跟二分搜索算法类似，它也是针对有序序列的搜索，只是它是通过搜索比较少的元素找到目标。当然它需要通过固定的跳跃间隔，这样它相比二分搜索效率提高了很多。

例如，假设我们有一个大小为 n 的数组 array 和要跳跃的步长为 m。 然后我们搜索索引 array[0]，array[m]，array[2m] ... ..array[km]等等。 一旦我们找到间隔（array[km] < x < array[(k + 1)m]），我们从索引 km 执行线性搜索操作来找到元素 x。

我们考虑以下数组：[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610]。数组的长度为16，跳跃搜索将以下列步骤找到值 55，假设跳跃的步长为 4：

1. 步骤1：从索引0跳转到索引4;
2. 步骤2：从索引4跳转到索引8;
3. 步骤3：从索引8跳转到索引16;
4. 步骤4：由于索引16处的元素大于55，因此我们将跳回一步到索引9。
5. 步骤5：从索引9执行线性搜索以获得元素55。

关于跳跃的大小数值确定，在最坏的情况下，我们必须进行 n / m 次跳转，如果最后一个检查值大于要搜索的元素，则我们对线性搜索进行 m-1 比较。 因此，最坏情况下的比较总数将为 ((n / m) + m -1)。 当 m = n\sqrt{n}n 时，函数 ((n / m) + m -1) 的值将为最小值。 因此，最好的步长是 m = n\sqrt{n}n。

该算法的特点：

1. 该算法仅适用于有序数组；
2. 要跳转的最佳大小为 O(n\sqrt{n}n)， 这使得跳跃搜索 O(n\sqrt{n}n) 的时间复杂度；
3. 跳跃搜索的时间复杂度在线性搜索 O(n\sqrt{n}n) 和二分搜索 O(log⁡n\log{n}logn) 之间；
4. 二分搜索算法相比跳跃搜索更好，但是跳跃搜索有以下优点：跳跃搜索仅遍历一次，而二分搜索最多需要 O(log⁡n\log{n}logn)，考虑要搜索的元素是最小元素或小于最小的），我们选用跳跃搜索；

JavaScript 实现：

function jumpSearch(arr, x) {
  const n = arr.length; // 数组长度
  let step = Math.floor(Math.sqrt(n)); // 定义步长为平方根向下取整
  let prev = 0; // 记录上一步的位置
  // 查找 x 在哪个块中
  while (arr[Math.min(step, n) - 1] < x) { 
    // 如果 x 在当前块中最大的数还小，那就要往前跳一个块
    prev = step; // 记录上一个块的位置
    step += Math.floor(Math.sqrt(n)); // 块的长度增加一个步长
   if (prev >= n) { 
      // 如果上一块已经到了末尾，说明 x 不在数组中
      return -1;
    }
  }
  // 线性搜索块中的元素
  while (arr[prev] < x) { 
    // 在当前块中线性查找
    prev++; // 指针向后移动
    if (prev === Math.min(step, n)) { 
      // 如果超出了当前块的范围，说明 x 不在数组中
      return -1;
    }
  }
  if (arr[prev] === x) { 
    // 找到了 x 的位置
    return prev;
  }
  return -1; // 没有找到 x
}
const arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
const x = 5;
const index = jumpSearch(arr, x);
console.log(index); // 4

Go 实现：

package main
import (
  "fmt"
  "math"
)
func jumpSearch(arr []int, x int) int {
    n := len(arr) // 数组长度
    step := int(math.Floor(math.Sqrt(float64(n)))) // 定义步长为平方根向下取整
    prev := 0 // 记录上一步的位置
    // 查找 x 在哪个块中
    for arr[int(math.Min(float64(step), float64(n))-1)] < x { 
        // 如果 x 在当前块中最大的数还小，那就要往前跳一个块
        prev = step // 记录上一个块的位置
        step += int(math.Floor(math.Sqrt(float64(n)))) // 块的长度增加一个步长
        if prev >= n { 
            // 如果上一块已经到了末尾，说明 x 不在数组中
            return -1
        }
    }
    // 线性搜索块中的元素
    for arr[prev] < x { 
        // 在当前块中线性查找
        prev++ // 指针向后移动
        if prev == int(math.Min(float64(step), float64(n))) { 
            // 如果超出了当前块的范围，说明 x 不在数组中
            return -1
        }
    }
    if arr[prev] == x { // 找到了 x 的位置
        return prev
    }
    return -1 // 没有找到 x
}
func main() {
    arr := []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
    x := 5
    index := jumpSearch(arr, x)
    fmt.Println(index) // 4
}

• 时间复杂度：O(n\sqrt{n}n)
• 辅助空间：O(1)

6、插值搜索

当我们从字典中搜索 “algorithm” 这个单词的时候，我们肯定不会傻傻地像二分搜索一样首先从中间开始。相反，我们会从首字母为 a 的地方开始搜索，然后根据第二个字母在字母表中的位置，找到相应的位置再继续搜索，这样重复这个过程，直到我们搜索到这个单词。

插值搜索（interpolation search）实际上是二分搜索的改良版。假设有这样一个数组 [0, 10, 20, 30, 40, 50, 60, 70, 80, 90]，我们可以发现，每个相邻元素的差均为 10，满足均匀分布。如果要搜索元素 70，我们首先可以计算数组中小于等于 70 的元素占所有元素的比例的期望值 p = (70 - 0) / (90 - 0) = 7 / 9，而数组的长度 n 我们知道等于 10，所以我们期望搜索的索引值就为 ⌊n × p⌋ = 7，对应的元素为 70，恰好就是我们要找的元素。这样，原本用二分法需要搜索 3 次的用插值搜索只用搜索 1 次，大大提高了搜索的效率。

这里，我们用一个公式来表示每次搜索的期望索引值：

其中，l 和 r 分别代表数组的第一个和最后一个索引，key代表待搜索的元素。跟二分搜索一样，如果一次搜索失败，数组的长度就相应地减小，再代入上面的公式继续搜索，直到搜索成功或失败。

插值搜索的平均复杂度为 O(loglognloglog{n}loglogn)，但证明过程相当的复杂，这里我们就不再讨论了。要是数组不是均匀分布的，插值搜索的复杂度会退化到线性的复杂度 O(n)。举一个极端的例子，假设数组为 [0, 99, 100, 100, 100]，我们要搜索元素 99。第一轮搜索我们计算出索引值为 3，第二轮为 2，第三轮为 1，这样我们搜索了三次。推广到含有 n 个元素的数组就需要搜索 n - 2 次，所以复杂度就为 Θ(n)。

因此，插值搜索的高效性只针对均匀分布的数组，而对于分布不均匀的数组，插值搜索便不再适用了。

JavaScript 实现：

function interpolationSearch(arr, low, high, x) {
  let pos
  // 因为数组是排序的，所以数组中的一个元素必须在角所定义的范围内
  if (low <= high && x >= arr[low] && x <= arr[high]) {
    // 在保持均匀分布的情况下探查位置。
    pos = low + Math.floor(((high - low) / (arr[high] - arr[low])) * (x - arr[low]))
    // 发现目标值的情况
    if (arr[pos] === x) {
      return pos
    }
    // 如果x比较大，x就在右边的子数组中
    if (arr[pos] < x) {
      return interpolationSearch(arr, pos + 1, high, x)
    }
    // 如果x比较小，x就在左边的子阵数组
    if (arr[pos] > x) {
      return interpolationSearch(arr, low, pos - 1, x)
    }
  }
  return -1
}

Go 实现：

func interpolationSearch(arr []int, x int) int {
    low, high := 0, len(arr)-1
    for low <= high && x >= arr[low] && x <= arr[high] {
        // 根据插值公式计算索引的估计值
        pos := low + int(float64(x-arr[low])*(float64(high-low)/float64(arr[high]-arr[low])))
        if arr[pos] == x {
            return pos
        } else if arr[pos] < x {
            low = pos + 1
        } else {
            high = pos - 1
        }
    }
    return -1
}

7、指数搜索

二分搜索，是一种分治算法，主要的思路是不断缩小排序数组中要查询的值可能存在的区间，每一次缩小一半。与二分搜索类似，指数搜索也是一种搜索固定值的分治算法，只不过它的空间范围是以指数形式缩小的。

指数搜索的大概过程如下图所示：
指数搜索同样需要数组是排序好的，如果数组是升序的，就从数组1号位开始，逐次检查元素是否小于等于要搜索的值，如果是，就把序号乘以2，以指数增长，如果不成立，就停止，留下当前的位置，假设是i。那么位置是0的元素怎么办呢？只能是在最开始的时候额外判断一下，如果位置是0的元素就是要找的值，那么就直接返回0，也就是元素的位置即可。

在上图的例子中，我们当然首先判断了一下位置为0的元素的值是否不等于要搜索的值，发现1≠9，那么说明要找的元素不在位置0，要继续寻找。然后我们要依次判断位置1，2，4，8的值是否小于等于要搜索的值，发现位置8元素小于等于9不成立，那么我们就停止判断，留下位置8。所以我们就知道，9肯定在[4, 8)中，注意这里是左闭右开区间，左闭的原因是，左边的位置判断元素≤9是成立的，也就是说左边界还是有可能等于9的，而右边界≤9不成立，所以肯定不可能等于9，故是左闭右开区间。

通过上面的过程，我们就成功地把9存在的区间范围，从整个数组的范围缩小到[4,8)中，在这个小范围内，我们无法继续进行指数搜索了，因为4已经很大了，再乘以2，就是8，都超过范围了，指数搜索失去了意义，但是[4,8)这段还是数组的一部分，数组元素还是有序的，所以我们可以使用二分搜索搜索[4,8)范围内9的位置，最终就可以找到9在位置6。

当然还有一种情况，那就是我们搜索的数是13，那么我们划定的范围就没有了右边界，这个时候数组的长度，就是右边界，也就是[8, 9)，当然这里还是取左开右闭区间，因为位置9在数组中实际上是不存在的，但由于是右开区间，故我们可以不用对数组长度进行-1的操作，直接填入即可，这就是我们为什么要判断每个位置≤要查询元素的原因。

时间复杂度：还是上面的图的例子，实际上指数搜索只涉及到了 [0,8] 的范围内，也就是 [0,i] 的范围，而且只比较了0，1，2，4，8五个值，第一个是一定要查询的，后面的个数和数值的位置有关系。 [0,i] 中，也不是每个元素都比较，而是只遍历 O(logilog{i}logi) 个元素，遍历完之后，还需要在[ i/2 , i ]内进行二分搜索，时间复杂度为 O(logi2log{\frac{i}{2}}log2i) 。所以整体时间复杂度就是：

O(logilog{i}logi) + O(logi2log{\frac{i}{2}}log2i) = O(logilog{i}logi) + O(logilog{i}logi) = 2O(logilog{i}logi) = O(logilog{i}logi)

JavaScript 实现：

function exponentialSearch(arr, val) {
  // 如果第一个元素匹配
  if (arr[0] === val) {
    return 0;
  }
  // 初始化范围大小为1
  let i = 1;
  const n = arr.length;
  while (i < n && arr[i] <= val) {
    i *= 2;
  }
  // 使用二分搜索在搜索范围内进行搜索
  return binarySearch(arr, Math.floor(i / 2), Math.min(i, n - 1), val);
}
function binarySearch(arr, left, right, val) {
  while (left <= right) {
    const mid = Math.floor(left + (right - left) / 2);
    if (arr[mid] === val) {
      return mid;
    } else if (arr[mid] < val) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  return -1;
}

Go 实现：

func exponentialSearch(arr []int, val int) int {
    // 如果第一个元素匹配
    if arr[0] == val {
        return 0
    }
    // 搜索范围并初始化范围大小为1
    i := 1
    n := len(arr)
    for i < n && arr[i] <= val {
        i *= 2
    }
    // 使用二分搜索法在搜索范围内进行搜索
    return binarySearch(arr, int(math.Floor(float64(i/2))), int(math.Min(float64(i), float64(n-1))), val)
}
func binarySearch(arr []int, left int, right int, val int) int {
    for left <= right {
        mid := int(left + (right - left) / 2)
        if arr[mid] == val {
            return mid
        } else if arr[mid] < val {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return -1
}

8、斐波那契搜索

斐波那契搜索是一种使用分而治之算法搜索已排序数组的方法，该算法借助斐波纳契数来缩小可能的位置。与二分搜索相比，排序数组被分成两个大小相等的部分，其中一个进一步检查，斐波那契搜索将数组分成两个部分，其大小为连续的斐波那契数。平均而言，这导致执行的比较增加了大约4％，但它的优点是只需要加法和减法来计算被访问数组元素的索引，而经典二分搜索需要比特移位，除法或乘法。斐波那契搜索具有O(lognlognlogn) 的平均和最差情况复杂度。总的来说是二分查找的一个优化。

Fibonacci序列具有一个数字是其前面两个连续数的总和的属性。因此，可以通过重复添加来计算序列。两个连续数字的比率接近黄金比率——1.618，二分搜索通过将搜索区域除以相等的部分 (1:1) 来工作。斐波那契搜索可以将其分成接近 1:1.618 的部分，同时使用更简单的操作。

黄金分割 点是指把一条 线段 分割为两部分，使其中一部分与全长之比等于另一部分与这部分之比。取其前三位数字的近视值是 0.618。由于按此比例设计的造型十分美丽，因此称为 黄金分割，也称为 中外比。这是一个神奇的数字，会带来意想不到的效果，比如《蒙娜丽莎的微笑》。

简单说，两条线的比例为 1:1.618，比如上图的头和身体的比例、鼻子和嘴巴下巴的比例。

对于一个 斐波那契数列：[1, 1, 2, 3, 5, 8, 13, 21, 34, 55]，我们会发现斐波那契数列的 两个相邻数的比例，无限接近 黄金分割值 0.618。

简单说：

3/2=1.5 、5/3=1.667、8/5=1.6、13/8=1.625 这样看来，他们的比例值是无限接近的 1.618 的
1/2=0.5 、3/5=0.6、5/8=0.625、8/13=0.6125 这样看，他们的比例值是无限接近  0.618 的

算法的主要思想如下图：

斐波那契数列性质 F[k] = F[k-1] + F[k-2]，由以上性质可以得到上图的组合: F[k]-1 = (F[k -1] -1) + (F[k-2] -1) + 1，那么说明：只要顺序表的长度为 F[k]-1，则可以将该表分成 长度为F[k-1]-1 和 F[k-2]-1 两段，如上图所示。那么中间值则为：mid = low + F[k-1]-1。

算法剖析：

斐波那契查找是依据斐波那契序列的特点对表进行分割的。假设开始时表中记录的个数(不妨设为n)比某个斐波那契数 (FuF_uFu) 小 1，即 n = FuF_uFu - 1（这也是一个前提条件），然后将给定值 key 和 a[Fu−1F_{u-1}Fu−1] 进行比较

• 若相等，则查找成功
• 若key < a[Fu−1F_{u-1}Fu−1]，则继续在 a[1] 至 a[Fu−1F_{u-1}Fu−1 - 1] 的子表中进行查找
• 若key > a[Fu−1F_{u-1}Fu−1]，则继续在 a[Fu−1F_{u-1}Fu−1 + 1] 至 a[FuF_{u}Fu - 1] 的子表中进行查找。该子表的长度为 Fu−2F_{u-2}Fu−2 - 1

为了更加直观的理解斐波那契查找的过程，我们借助下图进行一个简单的分析，按 ①~③ 的顺序

首先我们生成一个斐波那契数列： F1F_1F1 = 1, F2F_2F2 = 1， F3F_3F3 = 2， F4F_4F4 = 3， F5F_5F5 = 5， F6F_6F6 = 8， F7F_7F7 = 13；

然后我们设，有序表a, 从 a[1]~a[12] 的值为 1 ~ 12。（为了方便理解，储存该表的数组的a[0]为空），我们假定，需要查找的数为 key = 4。

因为 n = FuF_uFu - 1 ，可以知道此时，u = 7。将 key 和 a[F7F_7F7-1] （即 a[8]）进行比较，我们发现 key < a[8]。

然后在 a[1]~a[7] 中进行查找，此时 u = 6。将 key 和 a[F6F_6F6-1]（即a[5]）进行比较，我们发现key < a[5]。

然后再 a[1]~a[4] 中进行查找，此时 u = 5。将 key 和 a[F5F_5F5-1]（即a[3]）进行比较，我们发现 key > a[3]。

此时只剩 a[4]，查找完毕。

JavaScript 实现：

function fibMonaccianSearch(arr, value) {
  // 初始化斐波那契数
  let fibMMm2 = 0 
  let fibMMm1 = 1 
  let fibM = fibMMm2 + fibMMm1 
  // 计算最小的大于n的Fibonacci数
  while (fibM < arr.length) {
    fibMMm2 = fibMMm1
    fibMMm1 = fibM
    fibM = fibMMm2 + fibMMm1
  }
  let offset = -1
  while (fibM > 1) {
    // 检查arr[min(fibM, n)-1]是否为value
    const i = Math.min(offset + fibMMm2, arr.length - 1)
    if (arr[i] < value) {
      fibM = fibMMm1
      fibMMm1 = fibMMm2
      fibMMm2 = fibM - fibMMm1
      offset = i
    } else if (arr[i] > value) {
      fibM = fibMMm2
      fibMMm1 -= fibMMm2
      fibMMm2 = fibM - fibMMm1
    } else {
      return i
    }
  }
  if (fibMMm1 && arr[offset + 1] === value) {
    return offset + 1
  }
  return -1
}

Go 实现：

func fibonacciSearch(arr []int, value int) int {
    // 计算大于或等于数组长度的最小斐波那契数。
    fibMinus2, fibMinus1 := 0, 1
    fibCur := fibMinus2 + fibMinus1
    for fibCur < len(arr) {
        fibMinus2 = fibMinus1
        fibMinus1 = fibCur
        fibCur = fibMinus2 + fibMinus1
    }
    offset := -1
    for fibCur > 1 {
        i := min(offset+fibMinus2, len(arr)-1)
        if arr[i] < value {
            fibCur = fibMinus1
            fibMinus1 = fibMinus2
            fibMinus2 = fibCur - fibMinus1
            offset = i
        } else if arr[i] > value {
            fibCur = fibMinus2
            fibMinus1 = fibMinus1 - fibMinus2
            fibMinus2 = fibCur - fibMinus1
        } else {
            return i
        }
    }
    if fibMinus1 != 0 && offset+1 < len(arr) && arr[offset+1] == value {
        return offset + 1
    }
    return -1
}
func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}