查找算法
1. 线性查找
"""
线性查找:
对于被查找的序列没有顺序要求,可以是有序的,也可以是无序的,
查找时从线性表的起始位置按照顺序匹配,找到元素时,返回该元素在原始字符串的下标
若匹配完整个序列未找到匹配元素,则查找失败,返回-1
时间复杂度 O(n)
"""
def lineSearch(data_list, value):
count = 1
# 遍历所有下标
for i in range(len(data_list)):
print(f'第{count}次查找')
count += 1
# 若值匹配
if data_list[i] == value:
# 返回下标
return i
# 若遍历完未找到匹配元素 返回-1
return -1
if __name__ == '__main__':
data_list = [10, 20, 30, 45, 55, 67, 69, 73, 89, 92, 100]
print('*' * 30)
print('成功匹配' if lineSearch(data_list, 100) > 0 else '未找到')
print('成功匹配' if lineSearch(data_list, -1) > 0 else '未找到')
控制台输出
******************************
第1次查找
第2次查找
第3次查找
第4次查找
第5次查找
第6次查找
第7次查找
第8次查找
第9次查找
第10次查找
第11次查找
成功匹配
第1次查找
第2次查找
第3次查找
第4次查找
第5次查找
第6次查找
第7次查找
第8次查找
第9次查找
第10次查找
第11次查找
未找到
2. 二分查找
"""
二分查找:
要求被查找的序列必须是有序的,如果无序需要先进行排序再查找
查找时先对比目标序列的中间元素和目标值的大小,若中间元素等于目标值则查找成功
否则根据中间元素对比目标值的大小,结合目标序列的排列方式决定查找由中间元素分隔出来的左区间或右区间
"""
def binarySearch(data_list, value):
# 初始化 最小值对应的索引 最大值对应的索引
low, high = 0, len(data_list) - 1
# 计算中间索引
mid = len(data_list) // 2
count = 1
while low < high:
print(f'第{count}次查找')
count += 1
# 如果相同,返回下标值
if data_list[mid] == value:
return mid
# 中间元素大于目标值,搜索左边
elif data_list[mid] > value:
high = mid - 1
# 中间元素小于目标值,搜索右边
else:
low = mid + 1
mid = (high - low) // 2 + low
if __name__ == '__main__':
data_list = [10, 20, 30, 45, 55, 67, 69, 73, 89, 92, 100]
print('*' * 30)
print('成功匹配' if binarySearch(data_list, 100) else '未找到')
print('成功匹配' if binarySearch(data_list, -1) else '未找到')
控制台输出
******************************
第1次查找
第2次查找
第3次查找
未找到
第1次查找
第2次查找
第3次查找
未找到
3. 插值查找
"""
插值查找:
二分查找的改进
首先找到目标值所在的范围
它等于
当前最小值的索引 -- 索引的值
加上
(目标值 - 当前最小值) -- 真实值 - 索引对应的真实值
除以
(当前最大索引对应的值-当前最小索引对应的值) -- 索引对应的真实值 - 索引对应的真实值
乘以
(当前最大索引的值-当前最小索引的值) -- 索引值 - 索引值
得到
一个索引值 --得到接近 查找的值 的位置
如果这个估算的位置恰好存在于数组中，则返回该位置
如果不存在, 则比较估算位置的实际值与目标值
如果小于目标值则在右侧继续估算, 反之则在左侧
"""
def insertSearch(data_list, value):
# 初始化 最小值对应的索引 最大值对应的索引
low, high = 0, len(data_list) - 1
# 中间索引
mid = low + int((value - data_list[low]) / (data_list[high] - data_list[low]) * (high - low))
count = 1
while low < high:
print(f'第{count}次查找')
count += 1
# 如果相同,返回下标值
if data_list[mid] == value:
return mid
# 中间元素大于目标值,搜索左边
elif data_list[mid] > value:
high = mid - 1
# 中间元素小于目标值,搜索右边
else:
low = mid + 1
mid = low + int((value - data_list[low]) / (data_list[high] - data_list[low]) * (high - low))
if __name__ == '__main__':
data_list = [10, 20, 30, 45, 55, 67, 69, 73, 89, 92, 100]
print('*' * 30)
print('成功匹配' if insertSearch(data_list, 100) else '未找到')
print('成功匹配' if insertSearch(data_list, -1) else '未找到')
控制台输出
******************************
第1次查找
成功匹配
第1次查找
未找到
4. 斐波那契查找
"""
斐波那契查找:
斐波那契数列: F={1,1,2,3,5,8,13,21...}
表达式: F(i) = F(i-1) + F(i-2) (i>1)
二分查找的一种改进, 由于随着数字的增大,前一项和后一项的比值越来越接近黄金分隔比值是0.618
因此也成为黄金分割比例
流程:
斐波那契查找改变了mid的计算方式, mid = low + F(block-1) -1
block是斐波那契数列区间,F是斐波那契函数,用于获取斐波那契数列的第n个数
若目标值等于mid指向的数据,则返回mid值
若目标值大于mid指向的元素,则向右查找并减小两个斐波那契区间
若目标值小于mid指向的元素,则向左查找并减少一个斐波那契区间
重复上述步骤直到找到目标元素或区间为0或赋值,查找结束
时间复杂度 O(log₂n)
"""
def fibonacci(num):
"""
生成斐波那契数列
:param num:
:return:
"""
fib_list = [1, 1, 2]
a, b, c = 1, 1, 2
while c < num:
a = b
b = c
c = a + b
fib_list.append(c)
return fib_list
def fibonacciSearch(data_list, value):
# 初始化 最小值对应的索引 最大值对应的索引
low, high = 0, len(data_list) - 1
f = fibonacci(high)
# 初始区间为 斐波那契最后一个区间
block = len(f) - 1
# 计算中间索引
mid = low + f[block - 1] - 1
count = 1
while low <= high:
print(f'第{count}次查找')
count += 1
# 如果相同,返回下标值
if data_list[mid] == value:
return mid
# 中间元素大于目标值,搜索左边
elif data_list[mid] > value:
high = mid - 1
block -= 1
# 中间元素小于目标值,搜索右边
else:
low = mid + 1
block -= 2
mid = low + f[block - 1] - 1
if __name__ == '__main__':
data_list = [10, 20, 30, 45, 55, 67, 69, 73, 89, 92, 100]
print('*' * 30)
print('成功匹配' if fibonacciSearch(data_list, 100) else '未找到')
print('成功匹配' if fibonacciSearch(data_list, -1) else '未找到')
控制台输出
******************************
第1次查找
第2次查找
成功匹配
第1次查找
第2次查找
第3次查找
第4次查找
第5次查找
未找到