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

川长思鸟来 2022-12-19 13:24 133阅读 0赞

更多编程教程请到：[菜鸟教程][Link 1] https://www.piaodoo.com/

前提：升序数组，待查元素在数组中。

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

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

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)

第二次思考，简化中位数计算逻辑：

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)

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

运行测试：

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

结果如下：

![Image 1][]

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持菜鸟教程www.piaodoo.com。

[Link 1]: https://www.piaodoo.com/
[Image 1]:

发表评论取消回复

表情：

评论列表（有 0 条评论，133人围观）

还没有评论，来说两句吧...

相关阅读

相关 python二分查找

python二分查找 > 查找数据 > > import random > > nums = [random.randin

骑猪看日落/ 2022年12月24日 05:50/ 0 赞/ 144 阅读

相关基于python实现MQTT发布订阅过程原理解析

更多编程教程请到：[菜鸟教程][Link 1] https://www.piaodoo.com/ 友情链接：[好看站][Link 2] http://www.nrso.net

拼搏现实的明天。/ 2022年12月20日 15:48/ 0 赞/ 162 阅读

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

更多编程教程请到：[菜鸟教程][Link 1] https://www.piaodoo.com/ 前提：升序数组，待查元素在数组中。二分查找：就是一个递归函数c。待查元素

川长思鸟来/ 2022年12月19日 13:24/ 0 赞/ 134 阅读

相关 Python二分查找

> 二分查找又称折半查找，首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中

谁践踏了优雅/ 2022年07月14日 18:21/ 0 赞/ 195 阅读

相关二分查找 python

def binary_search(list, item): low = 0 high = len(list) - 1

逃离我推掉我的手/ 2022年05月17日 02:20/ 0 赞/ 220 阅读

相关用Python实现二分查找

用Python实现二分查找 2012-12-11 14:44:53 [我来说两句 ][Link 1] 作者：buaa\_shang 收藏 [![dl

快来打我*/ 2022年04月05日 07:18/ 0 赞/ 200 阅读

相关斐波那契查找原理解析

转载自[http://blog.chinaunix.net/uid-27164517-id-3313988.html][http_blog.chinaunix.net_uid-

刺骨的言语ヽ痛彻心扉/ 2022年03月15日 16:46/ 0 赞/ 301 阅读

相关 python实现二分查找算法

二分查找算法，是常见的搜索算法之一，适用于有序的序列，通过将序列不断的对折分为区间，从而确定查找值是否存在，优点是速度快。首先，假设表中元素是按升序排列，将表中间位置记录的

深藏阁楼爱情的钟/ 2022年02月14日 11:11/ 0 赞/ 265 阅读

相关折半查找（二分查找）-JAVA版

import java.util.Scanner; public class BinarySearch { /

﹏ヽ暗。殇╰゛Y/ 2022年01月22日 10:33/ 0 赞/ 274 阅读

相关 python实现二分查找

!/usr/bin/python -- coding:utf-8 -- 非递归实现二分查找 def bisearch1(lis,n

青旅半醒/ 2021年09月29日 00:48/ 0 赞/ 398 阅读