查找算法(一):查找

基于有序列表的查找。

线性查找

1
2
3
4
5
def search(arr, target):
for i in range(len(arr)):
if arr[i] == target:
return i
return -1

二分查找

二分查找(也称为折半查找),在给定一个有序数组的前提下,取中间的元素(arr[mid])作为比较的对象,如果target值大于中间元素,则在中间元素的右边继续查找,反之,则在中间元素的左边继续查找。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
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))
如果对您有帮助,您的一分钱赞赏也是对我莫大的鼓励~
0%