python 二进制查询示例代码
最编程
2024-07-07 10:06:41
...
对于要搜索的元素越多,二分查找速度比简单查找快的更多 这是二分查找算法的优点,但二分算法也有缺点,二分算法只针对有序的列表,这样插入和删除就会很困难,因此,折半查找方法只适合不经常变动的有序列表
二分查找有个很重要的特点,就是不会查找数列的全部元素,而查找的数据量其实正好符合元素的对数,正常情况下每次查找的元素都在一半一半地减少。所以二分查找的时间复杂度为 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二分法查找内容请搜索以前的文章或继续浏览下面的相关文章希望大家以后多多支持!
上一篇: 计网_计算机网络概述
下一篇: 在数组中查找关键字的 C++ 二分法
推荐阅读
-
[机器学习] - 线性回归(自我监督学习) - 10.示例代码(Python 实现)
-
Python实现分段收费的示例代码
-
用C均值聚类算法在Excel中轻松处理和分类数据(详解+Python代码示例)
-
如何在Python中轻松创建、调用和理解def函数,以及参数传递的实际操作与示例代码
-
用Python实际操作CSV文件的案例与代码示例
-
10个简单好玩又能快速入门的人工智能项目(包含Python示例代码)
-
如何使用Python从m3u8链接下载mp4视频:原理与源代码示例
-
用Python和SQLite3操作Chrome cookies的解密实战示例代码
-
Python 实现的因子分解机 (Factorization Machine) 代码示例
-
深入解析SILC超像素分割技术(配 Python 代码示例)