内容简介：二分查找（也称为折半查找），在给定一个斐波那契数列公式：斐波那契查找步骤如下：
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))
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持 码农网
猜你喜欢:
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
网站开发案例课堂：HTML5+CSS3+JavaScript网页设计案例课堂
刘玉红 / 2015-1-1 / 68
《网站开发案例课堂：HTML5+CSS3+JavaScript网页设计案例课堂》作者根据在长期教学中积累的网页设计教学经验，完整、详尽地介绍HTML 5 + CSS 3 + JavaScript网页设计技术。 《网站开发案例课堂：HTML5+CSS3+JavaScript网页设计案例课堂》共分24章，分别介绍HTML 5概述、HTML 5网页文档结构、HTML 5网页中的文本和图像、HTML......一起来看看 《网站开发案例课堂：HTML5+CSS3+JavaScript网页设计案例课堂》 这本书的介绍吧!
