枣阳城乡建设局网站,欧盟理事会,j建设网站,中网建站二分查找
查找的前提是数组有序
思路分析 代码实现
# 二分查找#xff08;递归法实现#xff09;
# 找到一个相等的值就返回该值的下标
def binary_search(arr: list, find_val: int, left: int, right: int):mid (left right) // 2 # 寻找数组中间位置的下标if left 递归法实现
# 找到一个相等的值就返回该值的下标
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,12341234,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 - 1k - 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 1k - 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)
