LeetCode - 二分查找(Binary Search)算法集合(Python)[左右边界|旋转数组|双列表]
欢迎关注我的CSDN：https://spike.blog.csdn.net/
本文地址：https://spike.blog.csdn.net/article/details/139419653
二分查找，也称为折半查找，是一种在有序数组中查找特定元素的高效算法。其基本原理是将待搜索的区间分成两半，然后根据中间元素与目标值的比较结果来确定下一步搜索的区间。这个过程会一直重复，直到找到目标元素或者搜索区间为空。二分查找，重要的是如何划分区间范围，移动左右指针。
二分查找的不同类型，包括：
- 基础的二分查找，包括各种不同形式，例如平方根、有序数组的单一元素
- 连续数左右边界的二分查找，熟练使用左右指针
- 旋转排序数组的二分查找，包括连续和不连续形式
- 双列表的联合二分查找
待做题目：
- 69. x 的平方根 、540. 有序数组中的单一元素
- 34. 在排序数组中查找元素的第一个和最后一个位置
- 33. 搜索旋转排序数组、81. 搜索旋转排序数组 II、153. 寻找旋转排序数组中的最小值、154. 寻找旋转排序数组中的最小值 II
- 4. 寻找两个正序数组的中位数
1. 二分查找
69. x 的平方根 - 二分查找，中值计算，注意细节，避免除数是0，默认返回r(右指针)
class Solution:def mySqrt(self, x: int) -> int:"""二分法，时间空间复杂度时间O(logx)，空间O(1)"""l, r = 0, x # 左右指针res = 0 # 最终值while l <= r: # 左小于右mid = l + (r - l) // 2 # 计算中值if mid == 0: # 避免除数是0return rs = x // midif mid <= s:res = mid # res取小值l = mid + 1else:r = mid - 1return res
540. 有序数组中的单一元素 - 二分查找
class Solution:def singleNonDuplicate(self, nums: List[int]) -> int:"""时间复杂度 O(logn)，空间复杂度 O(1)第1个元素下标是偶数，第2个元素下标是奇数"""n=len(nums)l,r=0,n-1while l<r:mid=l+(r-l)//2 # 计算中值if mid%2==0: # 中值是偶数位置if mid+1<n and nums[mid]==nums[mid+1]: # 常规条件l=mid+1 # 左移坐标else:r=midelse:if mid-1>=0 and nums[mid]==nums[mid-1]: # 常规条件l=mid+1 # 左移坐标else:r=midreturn nums[l] # 返回
2. 连续数左右边界的二分查找
34. 在排序数组中查找元素的第一个和最后一个位置 - 二分查找连续数的左右边界，注意：如何获得左边界和右边界，即先移动 r 还是先移动 l 的区别，同时注意右边界的位置-1。
class Solution:def searchRange(self, nums: List[int], target: int) -> List[int]:"""如何获取左右边界的问题，非常有趣，二分查找。时间复杂度O(logn)，空间O(1)"""def bs(nums, t, is_l):n = len(nums)l, r = 0, n - 1res = n # 初始化最大值while l <= r:mid = l + (r-l) // 2 # 判断是大于t，还是大于等于t# low-True nums[mid]>=t，优先r左移，其次l右移，r<l, res值小# high-False nums[mid]>t，优先l左移，其次r右移，r>l，res值大if (is_l and nums[mid] >= t) or nums[mid] > t:r = mid - 1res = mid # 保存大值else:l = mid + 1# print(f"[Info] is_l: {is_l}, r: {r}, l: {l}, mid: {nums[mid]}, t: {t}")return resn = len(nums)l = bs(nums, target, True)r = bs(nums, target, False) - 1 # 大于是前1位if l <= r and nums[l] == target and nums[r] == target:return [l, r]else:return [-1, -1]
3. 旋转数组的二分查找
33. 搜索旋转排序数组 - 旋转排序的二分查找
class Solution:def search(self, nums: List[int], target: int) -> int:"""旋转数组，只有一侧是有序的，只搜索有序一侧的值。时间O(logn)，空间O(1)"""n = len(nums)l, r = 0, n-1while l <= r:mid = l + (r-l) // 2 # 经典双指针起始if nums[mid] == target:return mid # 返回位置# 只搜索有序的一侧，即只移动有序的一侧的指针if nums[0] <= nums[mid]: # 左侧有序if nums[l] <= target < nums[mid]: # target左侧r = mid - 1 # 移动右指针else: # target右侧l = mid + 1 # 移动左指针else: # 右侧有序if nums[mid] < target <= nums[r]: # target右侧l = mid + 1 # 移动左指针else:r = mid - 1 # 移动右指针return -1 # 返回未找到
81. 搜索旋转排序数组 II - 旋转排序的二分查找，进阶含有重复元素
class Solution:def search(self, nums: List[int], target: int) -> bool:"""旋转数组，只有一侧是有序的，只搜索有序一侧的值，有相同元素时间O(logn)，空间O(1)"""n = len(nums)l, r = 0, n-1while l <= r:mid = l + (r-l) // 2 # 经典双指针起始if nums[mid] == target:return True # 返回位置if nums[mid] == nums[l]:l += 1 # 解决相同元素elif nums[mid] == nums[r]:r -= 1 # 解决相同元素elif nums[mid] < nums[r]: # 右区间是增序的if nums[mid] < target <= nums[r]: # target右侧l = mid + 1 # 移动左指针else:r = mid - 1 # 移动右指针else: # 左区间是增序的if nums[l] <= target < nums[mid]: # target左侧r = mid - 1 # 移动右指针else: # target右侧l = mid + 1 # 移动左指针return False # 返回未找到
153. 寻找旋转排序数组中的最小值 - 旋转排序的二分查找，注意和最右值比较，判断区间。
class Solution:def findMin(self, nums: List[int]) -> int:"""时间复杂度 O(logn)，空间复杂度 O(1)"""n = len(nums)l, r = 0, n-1while l < r:mid = l + (r-l) // 2# 中值小于右边界if nums[mid] <= nums[r]: # 避免l越界，优先移动rr = midelse: # 中值大于右边界l = mid+1return nums[l]
154. 寻找旋转排序数组中的最小值 II - 旋转排序的二分查找，包含重复数字
class Solution:def findMin(self, nums: List[int]) -> int:"""时间复杂度 O(logn)，空间复杂度 O(1)"""n = len(nums)l, r = 0, n - 1while l <= r:mid = l + (r-l)//2 # 计算中值if nums[mid]<nums[r]:r = midelif nums[mid]>nums[r]:l = mid+1else:r -= 1 # 避免重复return nums[l]
4. 双列表的联合二分查找
4. 寻找两个正序数组的中位数 - 双列表联合二分查找
class Solution:def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:"""时间复杂度O(log(m+n))，空间复杂度O(1)"""n1 = len(nums1)n2 = len(nums2)if n1 > n2:return self.findMedianSortedArrays(nums2,nums1)k = (n1 + n2 + 1)//2 # 中值l, r = 0, n1while l < r:m1 = l +(r - l)//2m2 = k - m1if nums1[m1] < nums2[m2-1]:l = m1 + 1else:r = m1m1 = lm2 = k - m1 c1 = max(nums1[m1-1] if m1 > 0 else float("-inf"), nums2[m2-1] if m2 > 0 else float("-inf") )if (n1 + n2) % 2 == 1:return c1c2 = min(nums1[m1] if m1 < n1 else float("inf"), nums2[m2] if m2 <n2 else float("inf"))return (c1 + c2) / 2
参考：
- CSDN - 二分法的专题总结——到底应该写小于还是小于等于、两个判断还是三个判断
- 二分查找