对于要搜索的元素越多,二分查找速度比简单查找快的更多 这是二分查找算法的优点,但二分算法也有缺点,二分算法只针对有序的列表,这样插入和删除就会很困难,因此,折半查找方法只适合不经常变动的有序列表
二分查找有个很重要的特点,就是不会查找数列的全部元素,而查找的数据量其实正好符合元素的对数,正常情况下每次查找的元素都在一半一半地减少。所以二分查找的时间复杂度为 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 -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
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]
总结