当前位置：首页 > news >正文

LeetCode | 二分法题型详解+图解

news 2025/6/20 12:27:48

在做 LeetCode 题时，是否使用二分法可以通过以下几个维度来判断。下面是一些常见信号和典型场景，帮助你判断是否可以或应该使用二分查找：

1.函数或数组在某一方向上是单调的（递增/递减）。

2.数据有序 or 可推导出有序逻辑

3.题目中有“最值”或“满足某个条件的最小值/最大值”描述

4.可能的输入规模较大（例如 1e5、1e9）且解空间连续

二分法常用模板

经典（闭区间）二分模板：

left, right = 0, n - 1
while left <= right:mid = (left + right) // 2if check(mid):right = mid - 1  # 或 left = mid + 1，根据目标是找左边界还是右边界else:left = mid + 1

总结：判断是否可以二分的 4 个关键词

特征	描述
单调性	满足某个条件的区间是连续的（左 False 右 True）
有序性	数组本身或逻辑上有序
范围型搜索	解的范围是一个区间而不是离散点
最值/边界类问题	问最小满足条件值 / 最大不满足条件值

【Leetcode 33】在排序和旋转的数组中搜索 (Search in Rotated Sorted Array)

给定一个升序排列的数组，经过旋转（无重复元素）后变成现在的样子，并给定一个目标值 target，请你在数组中搜索这个目标，如果找到了，返回它的索引；如果没找到，返回 -1。

解题思路：二分查找 + 逻辑判断

数组被分成了两个递增区间，我们不能直接用标准二分，而是要结合判断：

每次找中间值 mid
判断哪一边是有序的
再判断 target 落在哪一边
缩小区间继续查找

def search(nums,target):left,right=0,len(nums)-1while left<=right:mid =(left+right)//2if nums[mid]==target:return midif nums[left]<=nums[mid]:if nums[left]<=target<nums[mid]:right=mid-1else:left=mid+1else:if num[mid]<target<=nums[right]:left=mid+1else:right=mid-1return -1

【Leetcode 81 】在排序和旋转的数组中搜索Search in Rotated Sorted Array II

允许数组中存在重复元素，你仍然需要判断目标值是否存在，但现在由于重复值存在，无法通过某些条件唯一判断左右哪边有序，所以要更谨慎地处理边界情况。

关键思路：二分查找 + 有序区判断

虽然整体数组被打乱了，但它被分成了两个有序的子区间。

def search(nums,target):left,right=0,len(nums)-1while left <=right:mid=(left+right)//2if nums[mid]==tagrt:return Trueif nums[left]<nums[mid]if nums[left]<=tagrt <nums[mid]right=mid-1else:left=mid+1if nums[mid]<nums[right]:if nums[mid]< taget <=nums[right]left=mid+1else:right=mid-1#无法判断那边有序else:left+=1right -=1return False #时间复杂度：平均情况：O(log n)#最坏情况：O(n)（当所有元素都相等，比如 [1,1,1,1,1,1,1]）

举例：nums = [4,5,6,7,0,1,2], target = 0

初始：left=0, right=6
mid=3，nums[3]=7
→ 左边有序（4~7）
→ target=0 不在左边 → 去右边（left=4）
mid=5，nums[5]=1
→ 右边有序（1~2）
→ target=0 不在右边 → 去左边（right=4）
mid=4，nums[4]=0 ✅ 找到！

题号	是否允许重复	最优时间复杂度	最坏时间复杂度	特别处理
33	❌ 不允许	O(log n)	O(log n)	标准二分
81	✅ 允许	O(log n)	O(n)	加了 `left++` 和 `right--` 处理重复值

【Leetcode 153】Find Minimum in Rotated Sorted Array

给定一个无重复元素的升序旋转数组，找到其中的最小值。时间复杂度要求为 O(log n)。

def findMin(nums):left,right=0,len(nums)-1 # 设两个指针 left 和 right，从整个数组范围开始查找#每次取中间位置 mid，然后通过它和 right 比较，来判断最小值在哪一边。while left < right:min=(left+right)//2 # 找中间位置#如果中间的数比右边的大，说明最小值肯定在右边，因为当前 mid 比 right 大，所以最小值不可能是 mid，所以我们把左边界挪到 mid + 1if nums[mid]>nums[right]left=mid+1else:right=mid#当 left == right 的时候，说明找到了最小值的位置，直接返回即可。return nums[left]#时间复杂度：O(log n)（每次折半）#空间复杂度：O(1)（常数变量）

举例：nums = [4, 5, 6, 7, 0, 1, 2]

第一次：
- mid = 3 → nums[3] = 7 > nums[6] = 2 → 最小值在右边 → left = 4
第二次：
- mid = 5 → nums[5] = 1 < nums[6] = 2 → 最小值在左边或 mid → right = 5
第三次：
- mid = 4 → nums[4] = 0 < nums[5] = 1 → right = 4

此时 left == right == 4，返回 nums[4] = 0

【Leetcode 154】 Find Minimum in Rotated Sorted Array II

给定一个可能包含重复元素的升序旋转数组，找到最小值。
要求最优时间复杂度（接近 O(log n)，但由于有重复元素，最坏可能退化成 O(n)）

def findMin(nums):left, right = 0, len(nums) - 1 #两个指针 left 和 right 来包围可能包含最小值的区域，一开始是整个数组。while left < right:mid = (left + right) // 2 #每次查找中间值的位置。就像在“围住的区间”中切一刀。#三种情况分析：#情况1：中间值比右边的大，说明最小值一定在右边那一段if nums[mid] > nums[right]:left = mid + 1#情况2：中间值比右边小，说明右边那段是递增的，最小值要么在左边，elif nums[mid] < nums[right]:right = mid#情况3（关键！）如果 nums[mid] == nums[right]，我们没办法判断最小值在哪边！这是由于重复元素的存在造成的，else:right -= 1  # 不确定在哪边，只能收缩return nums[left]#时间复杂度分析
#平均情况：O(log n)（如果重复值不多）
#最坏情况：O(n)（全部重复或接近重复）

举例：数组[2, 2, 2, 0, 1]