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

川长思鸟来 2022-12-19 13:24 184阅读 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 条评论，184人围观）

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

相关阅读

相关 Python高效实现二分查找算法

Python高效实现二分查找算法 Python是一种高效的编程语言，经常被用来实现各种算法和数据结构。其中，二分查找算法是一种常用的算法，能够快速地在有序数组中查找目标元素。

缺乏、安全感/ 2024年03月25日 23:02/ 0 赞/ 187 阅读

相关 python实现二分查找

循环二分查找 def binarySearch(alist, key): left = 0 right = len(alist)

短命女/ 2023年07月19日 10:48/ 0 赞/ 57 阅读

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

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

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

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

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

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

相关用Python实现二分查找算法

1.概念 > 二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有

爱被打了一巴掌/ 2022年05月12日 03:12/ 0 赞/ 251 阅读

相关用Python实现二分查找

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

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

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

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

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

相关 python实现二分查找算法

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

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

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

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

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

相关 python实现二分查找

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

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