LeetCode - 二分查找(Binary Search)算法集合(Python)[左右边界|旋转数组|双列表]

欢迎关注我的CSDN：https://spike.blog.csdn.net/
本文地址：https://spike.blog.csdn.net/article/details/139419653

二分查找，也称为折半查找，是一种在有序数组中查找特定元素的高效算法。其基本原理是将待搜索的区间分成两半，然后根据中间元素与目标值的比较结果来确定下一步搜索的区间。这个过程会一直重复，直到找到目标元素或者搜索区间为空。二分查找，重要的是如何划分区间范围，移动左右指针。

二分查找的不同类型，包括：

1. 基础的二分查找，包括各种不同形式，例如平方根、有序数组的单一元素
2. 连续数左右边界的二分查找，熟练使用左右指针
3. 旋转排序数组的二分查找，包括连续和不连续形式
4. 双列表的联合二分查找

待做题目：

• 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 - 二分法的专题总结——到底应该写小于还是小于等于、两个判断还是三个判断
• 二分查找