package mainimport "fmt"// 二分查找：适合绝大多数随机存取的有序数据结构，如数组或内存中的数据。
// Fibonacci 查找：适合顺序存取数据结构，如磁带等顺序存取设备，也适合一些非完全随机访问的场景，例如大型数据库。// 生成 Fibonacci 数列，直到 fib[] 数列中的某个值 >= n
// 为什么？答：防止查找时k越界。
// 因为 Fibonacci 查找本质上与二分查找、插值查找是一致的，都是在划分查找范围。
// 不同的是，Fibonacci 查找划分出的范围比例近似为 0.618 : 0.382，这种比例来源于斐波那契数列的递推性质：
// F(k) = F(k-1) + F(k-2)。这使得每次查找都能以黄金分割的方式动态缩小范围。
//
// 在代码中，为了实现这样的划分，需要用斐波那契数列中的元素（fib[k], fib[k-1], fib[k-2]）动态划定查找范围：
// - 其中初次查找 0 + fib[k-1] - 1 作为划分点（检测点），将数组分为两部分：
// 左半区长度由 fib[k-1] 决定，右半区长度由 fib[k-2] 决定，是的，一般将划分点(检测点)定在左半区的最后一个元素处，这是规定 >_<
// 满足左半区与右半区的比例为 fib[k-1] : fib[k-2] ≈ 0.618 : 0.382。这样可以看出要查的数组长度范围变成了(fib[k-1]+fib[k-2])这是超出原数组长度的，所以一般要填充，之后会介绍填充部分的实现手法。
//
// 先看下具体划分流程
// 举个例子：
// 0 1 2 3 4 5 6 7 8 9
// 假设我们有一个长度为 10 的数组 [10, 22, 35, 40, 50, 60, 70, 80, 90, 100]，目标是寻找目标值 70。
// 1. 首先生成斐波那契数列，直到某个 fib[k] >= n（数组长度 10）：
// 斐波那契数列的前几项为 [0, 1, 1, 2, 3, 5, 8, 13...]。
// 找到 fib[6] = 13，因为 13 >= 10。这里意味着找到k=6
// 2. 然后划分数组：
// - 左部分长度为 fib[k-1] = fib[5] = 8，右部分长度为 fib[k-2] = fib[4] = 5。
// - 注意：由于 fib[k] = 13 超出数组长度，需要将数组扩展为长度 13，填充值一般定为原数组最后一个元素（如 100）。
// - 填充后：[10, 22, 35, 40, 50, 60, 70, 80, 90, 100, 100, 100, 100]
// - 划分点位置为 mid = low + fib[k-1] - 1 = 0 + 8 - 1 = 7。-> 划分点(检测点)定在左半区的最后一个元素处
// 3. 比较目标值与划分点的值：在升序数组中查找的话
// - 如果目标值小于划分点值（arr[mid]），缩小范围到左半区，此时区间长度由 fib[k-1] 决定。
// - 如果目标值大于划分点值（arr[mid]），缩小范围到右半区，此时区间长度由 fib[k-2] 决定。
// 4. 重复以上步骤，直到找到目标值或查找范围为空。
//
// 这种查找方法的核心是利用斐波那契数列的递推性质动态调整范围，
// 而不是像二分查找那样简单地平均划分为 1:1 的两部分。
//
// 注意事项：
// - 为了防止划分中间点后导致数组溢出，需要将数组填充至长度 >= fib[k]。
// - 填充值应为数组的最后一个元素，这样不会影响查找逻辑。
func generateFibonacci(n int) []int {fib := []int{0, 1} // 初始fibonaccifor fib[len(fib)-1] < n {fib = append(fib, fib[len(fib)-1]+fib[len(fib)-2])}return fib
}// 传入待查数组与目标
func fibonacciSearch(arr []int, target int) int {n := len(arr)if n == 0 {return -1 // 空待查数组，返回-1}// 1.生成 Fibonacci 数列// 这里根据待查数组的长度 n 生成一个足够大的 Fibonacci 数列，// 即找到一个数列，使 fib[k] 是第一个满足 fib[k] >= n 的斐波那契数。// 这样可以确保查找过程中的划分点 low+fib[k-1]-1 不会超出数组范围。//// 由于 Fibonacci 查找需要将数组长度扩展到至少 fib[k]，为避免数组越界// (你查找数组的左半区长度是到fib[k]为止，前面说了左半区最后一个元素定为划分点，现在右半区还要划分呢，所以要填fib[k-2])// 我们会在查找前对原数组进行填充操作，将不足部分用待查数组最后一个元素的值填充。// 这保证了即使查找范围超出原数组长度，仍然可以正确处理。fib := generateFibonacci(n)// 生成的 Fibonacci 数列通常会包含多个比 n 大的元素，超出了实际所需的最小 k。// 为了确定满足 fib[k] >= n 的最小 k，需要从数列末尾开始回退。// 通过以下循环找到这个最小 k：k := len(fib) - 1for fib[k] > n {k-- // 回退 k，直到找到满足 fib[k] >= n 的最小 k}// 循环退出时，初次查找时的 k 值已经确定，后续查找将从这个 k 开始。// 2. 填充数组，避免越界// 在之前生成的 Fibonacci 数列中，我们选择的 k 值可能会导致查找过程中超出原数组的范围。// 因此，需要将扩展后的数组填充至至少 fib[k] 长度。// 超出原待查数组部分的值，通常用原数组的最后一个元素填充，// 因为填充后的元素不会影响查找的逻辑，且可以避免数组越界。// 举例：// 原始待查数组: [10, 22, 35, 40, 50]// 扩展后的数组: [10, 22, 35, 40, 50, 50, 50, 50]extended := make([]int, fib[k]) // 为什么使用 fib[k] 作为扩展数组的长度?// 要满足扩展后的待查数组左半区与右半区之比0.618 : 0.382，fib[k] = fib[k-1] + fib[k-2]copy(extended, arr) // 复制原始待查数组的元素到扩展后的数组for i := n; i < len(extended); i++ {// 填充原数组之后的部分，用原数组最后一个元素填充，以避免数组越界extended[i] = arr[n-1] // 从索引 n 开始填充剩余部分}// 初始化查找区间low := 0 // 定义左指针// 查找for k > 0 {mid := low + fib[k-1] - 1 // 分割点if target < extended[mid] {k -= 1 // 在左半区} else if target > extended[mid] {low = mid + 1 // 在右半区，左指针右移k -= 2} else { // 找到if mid < n {return mid}return n - 1 // 如果找到的是填充值，返回原数组的最后一个值}}return -1 // 没找到
}func main() {// fibonacci 查不了数组长度小于等于2的？// 可以把这段加进fibonacciSearch// 特殊处理长度为 2 的情况，避免 Fibonacci 查找无法正确工作//if n == 2 {// if arr[0] == target {// return 0// } else if arr[1] == target {// return 1// } else {// return -1// }//}arr := []int{10, 22, 35, 40, 50, 60, 70, 80, 90, 100}target := 70index := fibonacciSearch(arr, target)// 输出结果if index != -1 {fmt.Printf("目标值 %d 在索引 %d\n", target, index)} else {fmt.Printf("目标值 %d 不在数组中\n", target)}
}
