对于要搜索的元素越多，二分查找速度比简单查找快的更多 这是二分查找算法的优点，但二分算法也有缺点，二分算法只针对有序的列表，这样插入和删除就会很困难，因此，折半查找方法只适合不经常变动的有序列表
二分查找有个很重要的特点，就是不会查找数列的全部元素，而查找的数据量其实正好符合元素的对数，正常情况下每次查找的元素都在一半一半地减少。所以二分查找的时间复杂度为 O(log2n) 是毫无疑问的。当然，最好的情况是只查找一次就能找到，但是在最坏和一般情况下的确要比顺序查找好了很多。
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 -1class 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 -1class 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二分法查找内容请搜索python博客以前的文章或继续浏览下面的相关文章希望大家以后多多支持python博客！
Powered By python教程网 鲁ICP备18013710号
python博客 - 小白学python最友好的网站!