目录
- 1、思路讲解(LC704)
- 2、代码思路讲解(循环不变量)
- (1) 左闭右闭
- (2)左闭右开
- (3)总结:左开右闭和左闭右开
- (4)复杂度分析
- 3. 习题分析
- (1)LC35 搜索插入位置 easy (二分查找法变种问题)
- 思路
- 代码
- (2)LC34 在排序数组中查找元素的第一个和最后一个位置 medium(有重复元素的情况)
- 思路1:二分查找+线性遍历
- 思路2:扩展二分查找
1、思路讲解(LC704)
LC704:给定一个长度为 n n n的数组 nums ,元素按从小到大的顺序排列且不重复。请查找并返回元素 target 在该数组中的索引。若数组不包含该元素,则返回-1。
暴力法思路: 从 n u m s [ 0 ] nums[0] nums[0]开始遍历一遍,time complexity = O ( n ) O(n) O(n)
二分法思路:
☀️首先要保证原序列是排好顺序的
2、代码思路讲解(循环不变量)
伪代码:
def func(nums , target) -> int:# 初始化首元素、尾元素left = 0right = len(nums) - 1 or len(nums)# 循环while 满足左指针在右指针的左边:# 理论上 Python 的数字可以无限大(取决于内存大小),无须考虑大数越界问题m = (i + j) // 2 # 计算中点索引 mif nums[m] < target:# 说明target在nums[m]的右侧移动leftelif nums[m] > target:# 说明target在nums[m]的左侧else:return m # 找到目标元素,返回其索引return -1 # 未找到目标元素,返回 -1
这里面有几个很容易出错的点(会导致循环不收敛
):
- while的循环条件是: l e f t < = r i g h t left<=right left<=right or l e f t < r i g h t left<right left<right
- 当nums[mid]<target的时候,应该是 l e f t = m i d + 1 left = mid+1 left=mid+1 or l e f t = m i d left = mid left=mid
- 当nums[mid]>target的时候,应该是 r i g h t = m i d − 1 right = mid - 1 right=mid−1 or r i g h t = m i d right = mid right=mid
这几个问题的答案是:你定义的区间是什么样子的?
(1) 左闭右闭
如果定义的区间是左闭右闭的情况: [ l e f t , r i g h t ] [left,right] [left,right]
- while的循环条件是: l e f t < = r i g h t left<=right left<=right (⭐️最推荐的选择,so easy)
- 因为当 l e f t = r i g h t left=right left=right 的时候, [ l e f t , r i g h t ] [left,right] [left,right]区间中仍然有一个元素,所以仍然是合法的
- 当nums[mid]<target的时候,应该是 l e f t = m i d + 1 left = mid+1 left=mid+1
- 因为当nums[mid]<target的时候,就证明了mid指向的值一定不是目标值,所以left不应该指向mid,而应该是mid+1
- 当nums[mid]>target的时候,应该是 r i g h t = m i d − 1 right = mid - 1 right=mid−1 or r i g h t = m i d right = mid right=mid
def binary_search(nums: list[int], target: int) -> int:"""二分查找(双闭区间)"""# 初始化双闭区间 [0, n-1] ,即 i, j 分别指向数组首元素、尾元素i, j = 0, len(nums) - 1# 循环,当搜索区间为空时跳出(当 i > j 时为空)while i <= j:# 理论上 Python 的数字可以无限大(取决于内存大小),无须考虑大数越界问题m = (i + j) // 2 # 计算中点索引 mif nums[m] < target:i = m + 1 # 此情况说明 target 在区间 [m+1, j] 中elif nums[m] > target:j = m - 1 # 此情况说明 target 在区间 [i, m-1] 中else:return m # 找到目标元素,返回其索引return -1 # 未找到目标元素,返回 -1
(2)左闭右开
如果定义的区间是左闭右开的情况: [ l e f t , r i g h t ) [left,right) [left,right)
- while的循环条件是: l e f t < r i g h t left<right left<right
- 因为当 l e f t = r i g h t left=right left=right 的时候, [ l e f t = r i g h t , r i g h t ) [left=right,right) [left=right,right)区间就会既有right又没有right,这种情况显然是不合法的
- 当nums[mid]<target的时候,应该是 l e f t = m i d + 1 left = mid+1 left=mid+1
- 因为当nums[mid]<target的时候,就证明了mid指向的值一定不是目标值,所以left不应该指向mid,而应该是mid+1
- 当nums[mid]>target的时候,应该是 r i g h t = m i d right = mid right=mid
- 因为区间是 [ l e f t , r i g h t ) [left,right) [left,right),当mid的值不是目标值的时候,区间应该是mid值前面的序列,但是因为右区间是开区间,所以可以直接将right指向mid。
def binary_search_lcro(nums: list[int], target: int) -> int:"""二分查找(左闭右开区间)"""# 初始化左闭右开区间 [0, n) ,即 i, j 分别指向数组首元素、尾元素+1i, j = 0, len(nums)# 循环,当搜索区间为空时跳出(当 i = j 时为空)while i < j:m = (i + j) // 2 # 计算中点索引 mif nums[m] < target:i = m + 1 # 此情况说明 target 在区间 [m+1, j) 中elif nums[m] > target:j = m # 此情况说明 target 在区间 [i, m) 中else:return m # 找到目标元素,返回其索引return -1 # 未找到目标元素,返回 -1
(3)总结:左开右闭和左闭右开
(4)复杂度分析
时间复杂度: O ( l o g n ) O(logn) O(logn) 每次循环区间减少一半,因此循环次数是 O ( l o g n ) O(logn) O(logn)
空间复杂度: O ( 1 ) O(1) O(1)没用使用数组啥的
3. 习题分析
(1)LC35 搜索插入位置 easy (二分查找法变种问题)
LC35:给定一个长度为 n n n的数组 nums ,元素按从小到大的顺序排列且不重复。给一个元素target,想要插入到nums中,并保持有序性。如果数组中存在target,就将targat插入到左侧;如果不存在,将target插入到按顺序插入的位置,返回索引。
思路
⭐️思考:
Q1: 当数组中有target的时候,插入点的索引是否就是返回值?
回答: yep!当查找到原数组有target值时,新的target要放在老的target的左侧,也就是说新的target代替了老的target的位置,也就是插入点的索引就是新插入的target的索引
Q2: 当数组不存在target的时候,新插入点是哪个元素的索引?
代码
def binary_search_insertion_simple(nums: list[int], target: int) -> int:"""二分查找插入点(无重复元素)闭区间"""i, j = 0, len(nums) - 1 # 初始化双闭区间 [0, n-1]while i <= j:m = (i + j) // 2 # 计算中点索引 mif nums[m] < target:i = m + 1 # target 在区间 [m+1, j] 中elif nums[m] > target:j = m - 1 # target 在区间 [i, m-1] 中else:return m # 找到 target ,返回插入点 m# 未找到 target ,返回插入点 ireturn i
(2)LC34 在排序数组中查找元素的第一个和最后一个位置 medium(有重复元素的情况)
给你一个按照非递减顺序排列的整数数组 nums,和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target,返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
思路1:二分查找+线性遍历
1️⃣ 执行二分查找,得到任意一个 target 的索引
2️⃣从找到的这个索引开始,分别向左和向右遍历,找到start和end指针
class Solution:def searchRange(self, nums: List[int], target: int) -> List[int]:if nums is None or len(nums) == 0:return [-1,-1]# 先用二分查找法找到target# 双闭区间(有重复元素)left = 0right = len(nums) - 1flag = 0while left <= right:mid = left + (right - left) // 2if target > nums[mid]: # 应该删除前半部分的元素left = mid + 1elif target < nums[mid]: # 应该删除后半部分的元素right = mid - 1else: # 当找到其中一个目标值之后,分别向前和向后遍历,找到起始和终止位置flag = 1start = midend = midwhile start >= 0 and nums[start] == target:start -= 1while end <= len(nums)-1 and nums[end] == target:end += 1breakif flag == 1:return [start+1,end-1]else:return [-1,-1]
时间复杂度: O ( n ) O(n) O(n),数组中存在很多重复的 target 时,该方法效率很低。
思路2:扩展二分查找
1️⃣查找左边界
- 查找到任意一个target
- 左边界 s t a r t start start必定在 [ l e f t , m i d − 1 ] [left,mid-1] [left,mid−1]中,所以可以将 r i g h t = m i d − 1 right=mid-1 right=mid−1,缩小区间,重新搜索一个新的target,新的target必定在源target的左侧
- 因为想要最左侧target的索引,所以和LC704是一样的,最后返回的是 s t a r t = m i d start=mid start=mid
2️⃣查找右边界
class Solution:def searchRange(self, nums: List[int], target: int) -> List[int]:if nums is None or len(nums) == 0:return [-1,-1]# 扩展二分查找法:查找target时候使用二分查找法,确定边界的时候仍然使用二分查找法# 先用二分查找法找到左边界# 双闭区间(有重复元素)left = 0right = len(nums) - 1start = -1while left <= right:mid = left + (right - left) // 2if target > nums[mid]: # 应该删除前半部分的元素left = mid + 1elif target < nums[mid]: # 应该删除后半部分的元素right = mid - 1else: # 当找到其中一个目标值之后# 左边界start应该在[left,mid]之间right = mid - 1start = mid# 再用二分查找法找到右边界left = 0right = len(nums) - 1end = -1while left <= right:mid = left + (right - left) // 2if target > nums[mid]: # 应该删除前半部分的元素left = mid + 1elif target < nums[mid]: # 应该删除后半部分的元素right = mid - 1else: # 当找到其中一个目标值之后# 右边界end应该在[mid,right]之间left = mid + 1end = mid return [start,end]
时间复杂度: O ( l o g N ) O(logN) O(logN)