Python实现二分法查找及优化的示例详解
作者:Python?集中营 发布时间:2023-10-12 14:20:44
二分查找法(Binary Search)是一种在有序数组中查找某一特定元素的算法,它的思想是将数组从中间分成两部分,判断目标元素在哪一部分中,然后继续在相应的部分中进行查找,直到找到目标元素或者确定目标元素不存在为止。
在本文中,我们将使用 Python 实现二分查找算法,并深入探讨算法的原理和实现细节。
1.二分查找的原理
二分查找法适用于有序数组中查找某一特定元素的场景,它的原理是将有序数组分成两个部分,每次取中间位置的元素与目标元素进行比较,根据比较结果确定要查找的元素在左边部分还是右边部分,然后继续在相应的部分中进行查找。
这样每次都能将待查找区间缩小一半,直到找到目标元素或者确定目标元素不存在为止。
二分查找法的时间复杂度为 O(log n),其中 n 表示数组的长度。这是因为每次查找都将查找区间缩小一半,最坏情况下需要查找 log n 次。
2.二分查找的实现
接下来,我们将使用 Python 实现二分查找算法。首先,我们定义一个函数binary_search,接收两个参数:一个有序数组 arr 和一个目标元素 target。
函数返回目标元素在数组中的下标,如果不存在则返回 -1。
def binary_search(arr, target):
left = 0
right = len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
在这个函数中,我们定义了两个指针 left 和 right,分别指向数组的第一个元素和最后一个元素。
然后,我们进入一个循环,直到 left > right 为止。在每次循环中,我们计算中间位置的下标 mid,并将 arr[mid] 与 target 进行比较。
如果 arr[mid] 等于 target,说明我们已经找到了目标元素,直接返回 mid。如果 arr[mid] 小于 target,说明目标元素在右边部分,我们将 left 指针移到 mid 的右边一位。
如果 arr[mid] 大于 target,说明目标元素在左边部分,我们将 right 指针移到 mid 的左边一位。这样不断缩小查找区间,直到找到目标元素或者确定目标元素不存在为止。下面是一个使用例子:
arr = [1, 3, 5, 7, 9]
target = 7
result = binary_search(arr, target)
if result == -1:
print("Element is not present in array")
else:
print("Element is present at index", result)
在这个例子中,我们定义了一个有序数组 arr 和一个目标元素 target,并调用了 binary_search 函数。
如果目标元素存在于数组中,函数将返回目标元素在数组中的下标;否则返回 -1。
在这个例子中,目标元素 7 存在于数组中,函数将输出 “Element is present at index 3”。
3.二分查找的优化
虽然二分查找法的时间复杂度为 O(log n),但是在实际应用中,我们可以通过一些优化来进一步提高算法的效率。
(1)查找区间的左右边界
在二分查找法中,我们需要定义一个查找区间,通常用 left 和 right 两个指针来表示。
在每次循环中,我们需要判断 left 和 right 是否重合,如果重合则说明查找区间为空,目标元素不存在于数组中。
这个判断过程需要进行多次,可以通过在循环条件中直接判断 left 和 right 是否相邻来减少判断次数,如下所示:
while left < right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
if arr[left] == target:
return left
else:
return -1
在这个优化中,我们将循环条件改为 left < right,这样每次循环结束后,left 和 right 最多相差 1。
在循环结束后,我们需要判断 left 和 right 是否指向目标元素。如果 arr[left] 等于 target,则说明目标元素存在于数组中,返回 left;否则返回 -1。
(2)位运算代替除法运算
在计算中间位置的下标 mid 时,我们通常使用除法运算符 //。然而,除法运算符比位运算符效率低得多,因此我们可以使用位运算符 >> 来代替除法运算符 //,如下所示:
mid = (left + right) >> 1
在这个优化中,我们将除以 2 改为右移 1 位,即将二进制数向右移动一位,相当于除以 2。这样可以减少计算中间位置的下标所需的时间。
(3)使用 bisect 库
Python 中的 bisect 库提供了一些实用的函数,可以帮助我们更方便地进行二分查找。
其中,bisect_left 函数和 bisect_right 函数分别用于在有序数组中查找某一元素的插入位置。
这两个函数的区别在于,当有多个相同的元素时,bisect_left 函数返回第一个位置,而 bisect_right 函数返回最后一个位置。
下面是一个使用 bisect 库进行二分查找的例子:
import bisect
arr = [1, 3, 5, 7, 9]
target = 7
index = bisect.bisect_left(arr, target)
if index < len(arr) and arr[index] == target:
print("Element is present at index", index)
else:
print("Element is not present in array")
在这个例子中,我们使用 bisect.bisect_left 函数在有序数组 arr 中查找目标元素 target 的插入位置。
如果插入位置小于数组长度,并且插入位置处的元素等于目标元素,则说明目标元素存在于数组中,输出其下标;否则输出 “Element is not present in array”。
4.总结
二分查找法是一种高效的查找算法,适用于有序数组中查找某一特定元素的场景。通过将数组从中间分成两部分,每次取中间位置的元素与目标元素进行比较,可以将待查找区间缩小一半,从而降低查找的时间复杂度。
在实现二分查找算法时,我们需要定义一个查找区间,通常用 left 和 right 两个指针来表示。在每次循环中,我们计算中间位置的下标 mid,并将 arr[mid] 与 target 进行比较。如果 arr[mid] 等于 target,说明我们已经找到了目标元素,直接返回 mid。
如果 arr[mid] 小于 target,说明目标元素在右边部分,我们将 left 指针移到 mid 的右边一位。如果 arr[mid] 大于 target,说明目标元素在左边部分,我们将 right 指针移到 mid 的左边一位。这样不断缩小查找区间,直到找到目标元素或者确定目标元素不存在为止。
在实际应用中,我们可以通过一些优化来进一步提高算法的效率。例如,可以在循环条件中直接判断 left 和 right 是否相邻来减少判断次数;可以使用位运算符 >> 来代替除法运算符 //,减少计算中间位置的下标所需的时间;可以使用 bisect 库提供的函数来进行二分查找,更方便地实现算法。
来源:https://mp.weixin.qq.com/s/KAvg2Lr_XnuNzMiGPqv9fQ
猜你喜欢
- 如: 2000-1-1==> 2000-01-01、2000-01-1==>2000-01-01、2000-1-01==>
- 一、python判断文件和文件夹是否存在、创建文件夹 >>> import os>>> os.
- 以下以CentOS 7.2为例,安装php的运行环境,首先打开php官网http://php.net/点击导航栏的Downloads进入下载
- 本文转自微信公众号:算法与编程之美一、引言在具备一定的Python编程基础以后,我们可以结合for循环进行多角星的编写,只要简单的几次循环,
- 前端开发部门在壮大,人员在增加,技术在进步。CSSer虽然不能代表前端开发团队,但CSSer是前端开发中非常重要的组成部分。一、文档写程序的
- 前言:有些时候,为了设定手机铃声或者发抖音视频,我们会耗费大量时间在剪辑音乐高潮部分上。那么这个音乐高潮的提取能不能自动化呢?当然可以。先来
- 对于时间数据,如2018-09-25 09:28:59,有时需要与Unix时间戳进行相互的运算,此时就需要对两种形式进行转换,在Python
- 前言今天制作的这一款能在B站能指定直播间、自动发弹幕的功能的脚本,因为没做那么多的功能,所以代码很简单,适合刚入门的同学学习先打开一个直播间
- css可以处理16,777,216颜色,可以使用名字、rgb值或十六进制代码。red红色等同于 rgb(255,0,0) &nbs
- 上一篇:微软建议的ASP性能优化28条守则(7)技巧 22:尽可能使用 Server.Transfer 代替 Response.Redire
- 本文实例讲述了Python基于SMTP协议实现发送邮件功能。分享给大家供大家参考,具体如下:SMTP(Simple Mail Transfe
- --利用T-SQL语句,实现数据库的备份与还原的功能 ----体现了SQL Server中的四个知识点: ----1. 获取SQL Serv
- 5月20日,微软正式提供了Windows XP下可用的雅黑字体下载,雅黑字体是一款近乎完美的字体,解决了宋体小文字无法辩认的问
- 1. 安装vim:# apt-get install -y vim-gnome2. 安装ctags,ctags用于支持tagli
- python socket多线程实现客户端与服务器连接,供大家参考,具体内容如下之前因为一些作业需要完成一个服务器监听多个客户端的程序,于是
- 以下摘录自 oreilly.JavaScript.The.Definitive.Guide.5th.Edition.Aug.200
- 实现过程最近在尝试openai的相关函数,所以今天就来盘点盘点下 createChatCompletion 函数,听说是专门为了聊天创立的a
- 网页版面布局的方法及技巧,版面指的是浏览器看到的完整的一个页面(可以包含框架和层)。因为每个人的显示器分辨率不同,所以同一个页面的大小可能出
- <%''调用例子'Dim int_RPP,int_Start,int_showNumberLink
- 一、控制用户存取 1、创建修改用户Creating Users Create/alter user new_user identified