服务器之家

服务器之家 > 正文

Pythonic版二分查找实现过程原理解析

时间:2020-08-11 23:55     来源/作者:天外归云

前提:升序数组,待查元素在数组中。

二分查找:就是一个递归函数c。待查元素a,当前数组中位数b,如果b=a则返回b的索引,b>a则在b左侧的子数组中调用函数c,否则在b右侧子数组中调用函数c。

第一次思考,按着上面的思路编程后的结果:

?
1
2
3
4
5
6
7
def binary_search(index, a, value):
  if a[(len(a) - 1) // 2] == value:
    return index + (len(a) - 1) // 2
  elif a[(len(a) - 1) // 2] < value:
    return binary_search(index + (len(a) - 1) // 2 + 1, a[(len(a) - 1) // 2 + 1:], value)
  else:
    return binary_search(index, a[0:(len(a) - 1) // 2 + 1], value)

第二次思考,简化中位数计算逻辑:

?
1
2
3
4
5
6
7
def binary_search(index, a, value):
  if a[len(a) // 2] == value:
    return index + len(a) // 2
  elif a[len(a) // 2] < value:
    return binary_search(index + len(a) // 2, a[len(a) // 2:], value)
  else:
    return binary_search(index, a[0:len(a) // 2], value)

第三次思考,去掉return,改为lambda形式:

binary_search = lambda index,a,value: index + len(a) // 2 if a[len(a) // 2] == value else binary_search(index + len(a) // 2, a[len(a) // 2:], value) if a[len(a) // 2] < value else binary_search(index, a[0:len(a) // 2], value)

以上就是二分查找变为“一行代码”版的过程。

运行测试:

?
1
2
3
if __name__ == '__main__':
  a = [1, 2, 33, 43, 52, 66, 88, 99, 111, 120]
  print(f"Target index: {binary_search(0, a, value=33)}")

结果如下:

Pythonic版二分查找实现过程原理解析

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持服务器之家。

原文链接:https://www.cnblogs.com/LanTianYou/p/8907354.html

相关文章

热门资讯

2022年最旺的微信头像大全 微信头像2022年最新版图片
2022年最旺的微信头像大全 微信头像2022年最新版图片 2022-01-10
蜘蛛侠3英雄无归3正片免费播放 蜘蛛侠3在线观看免费高清完整
蜘蛛侠3英雄无归3正片免费播放 蜘蛛侠3在线观看免费高清完整 2021-08-24
背刺什么意思 网络词语背刺是什么梗
背刺什么意思 网络词语背刺是什么梗 2020-05-22
yue是什么意思 网络流行语yue了是什么梗
yue是什么意思 网络流行语yue了是什么梗 2020-10-11
暖暖日本高清免费中文 暖暖在线观看免费完整版韩国
暖暖日本高清免费中文 暖暖在线观看免费完整版韩国 2021-05-08
返回顶部