python二分法查找实例代码(查找元素)

对于要搜索的元素越多，二分查找速度比简单查找快的更多这是二分查找算法的优点，但二分算法也有缺点，二分算法只针对有序的列表，这样插入和删除就会很困难，因此，折半查找方法只适合不经常变动的有序列表

二分查找有个很重要的特点，就是不会查找数列的全部元素，而查找的数据量其实正好符合元素的对数，正常情况下每次查找的元素都在一半一半地减少。所以二分查找的时间复杂度为 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二分法查找内容请搜索本站以前的文章或继续浏览下面的相关文章希望大家以后多多支持本站！

动态拨号：关键词排名下降是啥缘故，快速提高排名怎样做

排名优化：网站排名优化方法有什么，如何做有效果

老域名：怎样才算老域名，老域名建站有什么影响

内容优化：关键字排名要做哪些方面的优化，怎样做

技巧：网站转化率究竟是什么，有什么提升的技巧

一下吧：外贸站优化有哪些基本的做法和注意事项

概要：竞价推广费用大概要多少呢，竞价推广好不好

一下吧：SEO中site是什么意思，作用和应用是怎样的

邮箱：付费邮箱有哪些优势，付费邮箱挑选要考虑什么

集群是什么意思：集群是什么意思，都有哪些优势呢