内容简介：二分查找（也称为折半查找），在给定一个斐波那契数列公式：斐波那契查找步骤如下：
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))
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持 码农网
猜你喜欢:
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
Build Your Own Web Site the Right Way Using HTML & CSS
Ian Lloyd / SitePoint / 2006-05-02 / USD 29.95
Build Your Own Website The Right Way Using HTML & CSS teaches web development from scratch, without assuming any previous knowledge of HTML, CSS or web development techniques. This book introduces you......一起来看看 《Build Your Own Web Site the Right Way Using HTML & CSS》 这本书的介绍吧!
