python二分法查找实例代码
更新时间：2021年11月21日 20:50 点击：330 作者：栾沫
对于要搜索的元素越多，二分查找速度比简单查找快的更多 这是二分查找算法的优点，但二分算法也有缺点，二分算法只针对有序的列表，这样插入和删除就会很困难，因此，折半查找方法只适合不经常变动的有序列表
二分查找有个很重要的特点，就是不会查找数列的全部元素，而查找的数据量其实正好符合元素的对数，正常情况下每次查找的元素都在一半一半地减少。所以二分查找的时间复杂度为 O(log2n) 是毫无疑问的。当然，最好的情况是只查找一次就能找到，但是在最坏和一般情况下的确要比顺序查找好了很多。
题目一：给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
class Solution:
def search(self,nums:List[int],target:int)->int:
left=0
right=len(nums)-1
while(left<=right):
mid=(left+right)//2
if nums[mid]==target:
return mid
if nums[mid]<target:
left=mid+1
else:
right=mid-1
return -1
题目二：在一个严格递减的数组中，找到第二个比目标值target大的数的下标。若不存在，则返回-1。
class Solution:
def search(self,nums:List[int],target:int)->int:
left=0
right=len(nums)-1
while(left<=right):
mid=(left+right)//2
if nums[mid]==target:
return mid
if nums[mid]>target:
left=mid+1
else:
right=mid-1
return -1
题目三：函数应该以长度为 2 的整数数组的形式返回这两个数的下标值。numbers 的下标 从 1 开始计数 ，所以答案数组应当满足 1 <= answer[0] < answer[1] <= numbers.length 。你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。
class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
for i in range(len(numbers)-1):
left=i
right=len(numbers) - 1
while(left<=right):
mid=(left+right)//2
if numbers[mid]+numbers[i]==target:
return [i+1,mid+1]
elif numbers[mid]+numbers[i]<target:
left=mid+1
else:
right = mid-1
return [-1,-1]
总结
到此这篇关于python二分法查找的文章就介绍到这了,更多相关python二分法查找内容请搜索猪先飞以前的文章或继续浏览下面的相关文章希望大家以后多多支持猪先飞！
原文出处：https://blog.csdn.net/weixin_51458838/article/details/121432
相关文章
- 这篇文章主要介绍了python-opencv-画外接矩形框的实例代码，代码简单易懂，对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-09-04
Python astype(np.float)函数使用方法解析
这篇文章主要介绍了Python astype(np.float)函数使用方法解析,文中通过示例代码介绍的非常详细，对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下...2020-06-08- 2022虎年新年即将来临，小编为大家带来了一个利用Python编写的虎年烟花特效，堪称全网最绚烂，文中的示例代码简洁易懂，感兴趣的同学可以动手试一试...2022-02-14
- 在本篇文章里小编给大家分享的是一篇关于python中numpy.empty()函数实例讲解内容，对此有兴趣的朋友们可以学习下。...2021-02-06
python-for x in range的用法(注意要点、细节)
这篇文章主要介绍了python-for x in range的用法，具有很好的参考价值，希望对大家有所帮助。一起跟随小编过来看看吧...2021-05-10- 这篇文章主要介绍了Python 图片转数组,二进制互转操作，具有很好的参考价值，希望对大家有所帮助。一起跟随小编过来看看吧...2021-03-09
- 这篇文章主要介绍了Python中的imread()函数用法说明，具有很好的参考价值，希望对大家有所帮助。一起跟随小编过来看看吧...2021-03-16
- 这篇文章主要介绍了python如何实现b站直播自动发送弹幕，帮助大家更好的理解和学习使用python，感兴趣的朋友可以了解下...2021-02-20
python Matplotlib基础--如何添加文本和标注
这篇文章主要介绍了python Matplotlib基础--如何添加文本和标注，帮助大家更好的利用Matplotlib绘制图表，感兴趣的朋友可以了解下...2021-01-26- 这篇文章主要介绍了解决python 使用openpyxl读写大文件的坑，具有很好的参考价值，希望对大家有所帮助。一起跟随小编过来看看吧...2021-03-13
- 今天小编就为大家分享一篇python 计算方位角实例(根据两点的坐标计算)，具有很好的参考价值，希望对大家有所帮助。一起跟随小编过来看看吧...2020-04-27
- 这篇文章主要为大家详细介绍了python实现双色球随机选号，文中示例代码介绍的非常详细，具有一定的参考价值，感兴趣的小伙伴们可以参考一下...2020-05-02
- 在本篇文章里小编给大家整理的是一篇关于python中使用np.delete()的实例方法，对此有兴趣的朋友们可以学习参考下。...2021-02-01
- 这篇文章主要介绍了使用Python的pencolor函数实现渐变色功能,本文通过实例代码给大家介绍的非常详细，对大家的学习或工作具有一定的参考借鉴价值，需要的朋友可以参考下...2021-03-09
- 这篇文章主要介绍了python自动化办公操作PPT的实现，文中通过示例代码介绍的非常详细，对大家的学习或者工作具有一定的参考学习价值，需要的朋友们下面随着小编来一起学习学习吧...2021-02-05
Python getsizeof()和getsize()区分详解
这篇文章主要介绍了Python getsizeof()和getsize()区分详解，文中通过示例代码介绍的非常详细，对大家的学习或者工作具有一定的参考学习价值，需要的朋友们下面随着小编来一起学习学习吧...2020-11-20- 这篇文章主要介绍了PyTorch一小时掌握之迁移学习篇，本文给大家介绍的非常详细，对大家的学习或工作具有一定的参考借鉴价值，需要的朋友可以参考下...2021-09-08
- 这篇文章主要为大家详细介绍了python实现学生通讯录管理系统，文中示例代码介绍的非常详细，具有一定的参考价值，感兴趣的小伙伴们可以参考一下...2021-02-25
- 这篇文章主要介绍了解决python 两个时间戳相减出现结果错误的问题，具有很好的参考价值，希望对大家有所帮助。一起跟随小编过来看看吧...2021-03-12
- 这篇文章主要介绍了Python绘制的爱心树与表白代码,本文通过实例代码给大家介绍的非常详细，对大家的学习或工作具有一定的参考借鉴价值，需要的朋友可以参考下...2021-04-06