查找算法：二分查找、插值查找、斐波那契查找

二分查找

查找的前提是数组有序

思路分析

代码实现

# 二分查找（递归法实现）
# 找到一个相等的值就返回该值的下标
def binary_search(arr: list, find_val: int, left: int, right: int):mid = (left + right) // 2  # 寻找数组中间位置的下标if left > right:  # 找不到元素，返回-1return -1if find_val == arr[mid]:  # 找到了元素，返回元素在数组中的下标return midelif find_val < arr[mid]:  # 要找的元素比数组中间元素小，则继续在 mid 的左边寻找return binary_search(arr, find_val, left, mid - 1)else:  # 要找的元素比数组中间元素大，则继续在 mid 的右边寻找return binary_search(arr, find_val, mid + 1, right)arr = [4, 8, 9, 10, 12, 14, 15]
res = binary_search(arr, 0, 0, len(arr) - 1)
print(res)# 二分查找（递归法实现）
# 如果数组中有多个值和要查找的值相等，则把它们的下标都返回
def binary_search2(arr: list, find_val: int, left: int, right: int):mid = (left + right) // 2  # 寻找数组中间位置的下标if left > right:  # 找不到元素，返回-1return []if find_val == arr[mid]:  # 找到了元素，返回元素在数组中的下标# 找到了元素，先把当前的下标放入到一个列表中# 再依次从该位置开始向左和向右查找，还有没有其他相等的值index_pos = []index_pos.append(mid)temp = mid - 1while True:  # 向左查找if temp < left or arr[temp] != find_val:breakindex_pos.append(temp)temp -= 1  # temp 左移temp = mid + 1while True:  # 向右查找if temp > right or arr[temp] != find_val:breakindex_pos.append(temp)temp += 1  # temp 右移return index_poselif find_val < arr[mid]:  # 要找的元素比数组中间元素小，则继续在 mid 的左边寻找return binary_search2(arr, find_val, left, mid - 1)else:  # 要找的元素比数组中间元素大，则继续在 mid 的右边寻找return binary_search2(arr, find_val, mid + 1, right)arr = [4, 8, 9, 10,10, 12, 14, 15]
res = binary_search2(arr, 0, 0, len(arr) - 1)
print(res)

插值查找

查找的前提是数组有序

思路分析

当数组为[1, 2, 3, 4, 5, ..., 100] 时，加入此时要查找1，那么二分查找的方法会进行多次递归才能找到，效率较低，所以有了插值查找方法。插值查找适用于数据比较连续的情况下。

代码实现

# 插值查找
def insert_value_search(arr: list, find_val: int, left: int, right: int):# 找不到元素，返回-1# 条件 find_val < arr[left] or find_val > arr[right] 要有，否则mid可能会越界if left > right or find_val < arr[left] or find_val > arr[right]:  return -1# 寻找数组中间位置的下标mid = left + (right - left) * (find_val - arr[left]) // (arr[right] - arr[left])mid_val = arr[mid]if find_val == mid_val:  # 找到了元素，返回元素在数组中的下标return midelif find_val < mid_val:  # 要找的元素比数组中间元素小，则继续在 mid 的左边寻找return binary_search(arr, find_val, left, mid - 1)else:  # 要找的元素比数组中间元素大，则继续在 mid 的右边寻找return binary_search(arr, find_val, mid + 1, right)arr = []
for i in range(100):arr.append(i + 1)
res = insert_value_search(arr, 3, 0, len(arr) - 1)
print(res)

斐波那契查找

查找的前提是数组有序

思路分析

代码实现

import copy
# 斐波那契查找
# 因为算法中需要用到斐波那契数列，所以此处用非递归的方法构造一个斐波那契数列
def fib(size: int) -> list:f = []f.append(1)f.append(2)i = 2while i < size:f.insert(i, f[i - 1] + f[i - 2])i += 1return f# 非递归方式实现斐波那契查找算法
def fibonacci_search(arr, key):low = 0high = len(arr) - 1k = 0  # 表示斐波那契分割数值的下标mid = 0  # 存放 mid 值f = fib(20)  # 获取斐波那契数列# 获取斐波那契分割数值的下标while high > f[k] - 1:k += 1# 因为f[k]的值可能大于arr的长度，因此需要对数组进行扩容（新构造一个数组）# 让数组的长度等于f[k]，新增加的长度的下标用arr数组最后的数填充# 如：arr=[1,8,10,89,1000,1234]  f[k] = 8# 扩容后：temp=[1,8,10,89,1000,1234，1234,1234]temp = copy.deepcopy(arr)i = high + 1while i < f[k]:temp.append(arr[high])i += 1# 使用 while 来循环处理，找到要查找的keywhile low <= high:  # 只要条件满足就可以继续查找mid = low + f[k - 1] - 1if key < temp[mid]:  # 应该继续向数组的前面查找（左边）high = mid - 1"""k -= 1 说明：数组全部元素 = 前面（左边）的元素 + 后面（右边）的元素斐波那契数列：f[k] = f[k - 1] + f[k - 2]因为前面有f[k - 1]个元素，所以可以继续拆分：f[k - 1] = f[k - 2] + f[k - 3]即在f[k - 1] 的前面继续查找，即下次循环 mid = f[k - 1 - 1] - 1 """k -= 1elif key > temp[mid]:  # 应该继续向数组的后面查找（右边）low = mid + 1"""k -= 2  说明：数组全部元素 = 前面（左边）的元素 + 后面（右边）的元素斐波那契数列：f[k] = f[k - 1] + f[k - 2]因为后面有f[k - 2]个元素，所以可以继续拆分：f[k - 2] = f[k - 3] + f[k - 4]即在f[k - 2] 的前面继续查找 k-=2，即下次循环 mid = f[k - 1 - 2] - 1 """k -= 2else:  # 找到# 确定返回的是哪个下标if mid <= high:return midreturn high# 找不到，返回-1return -1arr=[1,8,10,89,1000,1234]
res = fibonacci_search(arr, 8)
print(res)