内容简介：二分查找（也称为折半查找），在给定一个斐波那契数列公式：斐波那契查找步骤如下：
def search(arr, target):
for i in range(len(arr)):
if arr[i] == target:
return i
return -1
二分查找
二分查找（也称为折半查找），在给定一个 有序数组 的前提下，取中间的元素（arr[mid]）作为比较的对象，如果target值大于中间元素，则在中间元素的右边继续查找，反之，则在中间元素的左边继续查找。
def binary_search(arr, target):
lo = 0
hi = len(arr)-1
while lo <= hi:
mid = (lo + hi) // 2
if arr[mid] == target:
return mid
elif arr[mid] > target:
hi = mid - 1
else:
lo = mid + 1
return -1
斐波那契数列查找
斐波那契数列公式：
斐波那契查找步骤如下：
第一步：从斐波那契数列中找到 第一个 大于或等于数组长度（n）的数（fibM）
第二步：当数组中还有未遍历的元素时：
1. 将游标cur定义为fib2覆盖部分的最后一个元素 2. 比较目标值与arr[cur]进行比较，如果匹配，立即返回索引，完成查找 3. 如果目标值大于arr[cur]，则把斐波那契数列下降一个单位 4. 如果目标值小于arr[cur]，则把斐波那契数列下降两个单位
第三步：如果仅余一个元素用于比较，检验fib1是否等于1，如果是，判断该元素是否为target
def fibMonaccianSearch(arr, target, n):
# f(n) = f(n-1) + f(n-2)
# fib2 + fib1 = fibM
# fib2 --> fib1 --> fibM
fib2 = 0
fib1 = 1
fibM = fib2 + fib1
while fibM < n: # 从斐波那契数列中找到*第一个*大于或等于数组长度（n）的数（fibM）
fib2 = fib1
fib1 = fibM
fibM = fib2 + fib1
offset = -1
while fibM > 1: # 当fibM等于1，fib2等于0，后面没有元素了
cur = min(offset+fib2, n-1) # cur相当于二分查找中的mid
if arr[cur] < target: # target大于arr[cur]，转向cur的右边
fibM = fib1 # 斐波那契下降一个单位
fib1 = fib2
fib2 = fibM - fib1
offset = cur # cur的右边需要把cur之前的部分加到fib2上
elif arr[cur] > target: # target小于arr[cur]，转向cur的左边
fibM = fib2 # 斐波那契下降两个单位
fib1 = fib1 - fib2
fib2 = fibM - fib1
else:
return cur
if fib1 == 1 and arr[offset+1] == target:
# 如果仅余一个元素用于比较，检验fib1是否等于1，如果是，判断该元素是否为target
return offset+1
# element not found. return -1
return -1
# Driver Code
arr = [10, 22, 35, 40, 45, 50, 80, 82, 85, 90, 100]
n = len(arr)
target = 10
print("Found at index:", fibMonaccianSearch(arr, target, n))
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持 码农网
猜你喜欢:
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
HTML 5实战
陶国荣 / 机械工业出版社 / 2011-11 / 59.00元
陶国荣编著的《HTML5实战》是一本系统而全面的HTML 5教程，根据HTML 5标准的最新草案，系统地对HTML 5的所有重要知识点进行了全面的讲解。在写作方式上，本书以一种开创性的方式使理论与实践达到极好的平衡，不仅对理论知识进行了清晰而透彻的阐述，而且根据读者理解这些知识的需要，精心设计了106个完整（每个案例分为功能描述、实现代码、效果展示和代码分析4个部分）的实战案例，旨在帮助读者通过实......一起来看看 《HTML 5实战》 这本书的介绍吧!
