斐波那契查找（Fibonacci Search）

# /*
# 斐波那契查找（Fibonacci Search）
# --------------------------------------------------------
# 原理：
# 针对有序序列的一种查找方法。
# 利用斐波那契数列来确定待查区间的分割点，
# 通过减小区间长度逐步逼近目标值。
#
# 与二分查找类似，但分割点不一定在中间，
# 对于某些序列性能略优。
# */

def fibonacci_search(arr, target):
    n = len(arr)

    # 生成足够大的斐波那契数列
    fibM_minus_2 = 0   # (m-2)项
    fibM_minus_1 = 1   # (m-1)项
    fibM = fibM_minus_1 + fibM_minus_2  # m项

    while fibM < n:
        fibM_minus_2 = fibM_minus_1
        fibM_minus_1 = fibM
        fibM = fibM_minus_1 + fibM_minus_2

    offset = -1

    while fibM > 1:
        i = min(offset + fibM_minus_2, n - 1)

        if arr[i] < target:
            fibM = fibM_minus_1
            fibM_minus_1 = fibM_minus_2
            fibM_minus_2 = fibM - fibM_minus_1
            offset = i
        elif arr[i] > target:
            fibM = fibM_minus_2
            fibM_minus_1 -= fibM_minus_2
            fibM_minus_2 = fibM - fibM_minus_1
        else:
            return i

    # 检查最后一个可能位置
    if fibM_minus_1 and offset + 1 < n and arr[offset + 1] == target:
        return offset + 1

    return -1


# 示例演示（必须是有序列表）
data = [10, 22, 35, 40, 45, 50, 80, 82, 85, 90, 100]
print("数据：", data)

pos = fibonacci_search(data, 85)
print("查找 85 的位置:", pos)

pos = fibonacci_search(data, 25)
print("查找 25 的位置:", pos)

# --------------------------------------------------------
# 关键要点总结：
# 1) 利用斐波那契数列确定分割点而非中点；
# 2) 对有序序列有效；
# 3) 时间复杂度 O(log n)，空间复杂度 O(1)；
# 4) 查找过程中区间长度逐步缩小；
# 5) 对数据量大且对分割点有优化需求的场景适用；
# 6) 与二分查找相比，减少某些情况下的访问次数。
# */

# 数据： [10, 22, 35, 40, 45, 50, 80, 82, 85, 90, 100]
# 查找 85 的位置: 8
# 查找 25 的位置: -1