今天仍然做二分查找相关的题目。先来回顾一下二分查找的方法和使用的条件。二分查找是在数组中查找目标值的一种方法,通过边界索引确定中间索引,判断中间索引处的元素值和目标值的大小,来不断缩小查找区间。使用二分查找有如下一些限制:
- 数组是单调递增或单调递减;
- target值唯一。
话不多说,直接上题!
1.题目链接
题目名称:在排序数组中查找元素的第一个和最后一个位置
题目详情:
非减顺序排列的整数数组 nums,和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target,返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
示例 1:
输入:nums = [5,7,7,8,8,10], target = 8
输出:[3,4]
示例 2:
输入:nums = [5,7,7,8,8,10], target = 6
输出:[-1,-1]
示例 3:
输入:nums = [], target = 0
输出:[-1,-1]
解法一:我自己写出来的!明天奖励自己吃个鸡腿,哈哈哈哈
主要思路:
首先题目中给定的数组是非减顺序,其实不符合二分查找的条件,但是题目最终是要找到等于target的开始位置和结束位置。这里可以分为三种情况:
(1) target不在数组中,则和普通的二分查找方式一样;
(2) target在数组中,但有且仅有一个,那也和普通的二分查找一样;
(3) target在数组中,但个数不止一个,这种情况下当nums[mid] == target时,首先就可以把mid存储起来,其次因为在当前这个区间内不止一个target,所以不能按照以前的方式直接返回或确定当前mid左侧的值一定全部小于target,mid右侧的值一定全部大于target。故这里就会以mid为节点,分成两个子区间[lindex,mid-1]和[mid+1,rindex],两个子区间分别再进行二分查找,寻找满足条件的索引。
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
# 设定一个list,用来存储数组中等于target的索引
# 且out要么为空要么有且仅有两个元素,包括左边界和右边界
out=[]
def run(lindex,rindex):
if lindex > rindex:
return -1
mid=lindex+(rindex-lindex)//2
# 当mid索引元素不等于target时,像之前普通二分查找法一样
if nums[mid] != target:
if nums[mid]>target:
rindex=mid-1
else:
lindex=mid+1
return run(lindex,rindex)
# 当mid索引元素==target时
else:
if len(out) == 0:
# 若当前mid是第一个判断为target的索引,则填充至out
out.extend([mid,mid])
else:
# 当满足条件的索引大于1个时,
# 则这里判断当前索引是左边界还是右边界
out[0]=min(out[0],mid)
out[1]=max(out[1],mid)
# 当mid索引==target时,需将[lindex,rindex]划分成两个子区间
# 分别进行二分查找,继续搜索==target的索引
run(lindex,mid-1)
run(mid+1,rindex)
run(0,len(nums)-1)
if len(out) == 0:
return [-1,-1]
return out
解法二:看的代码随想录的解法,可以学习这种思路
解题思路:
这里使用两次二分法分别去查找target的左边界和右边界(特别注意的是,这里的左边界指的是第一个target索引的前面一位索引,右边界也是一样),也可以分为三种情况去讨论,分别是:
(1) target小于数组的最小值或大于数组的最大值,即在数组范围的左侧或右侧;
(2) target在数组范围内,但target不在数组中;
(3) target在数组中。
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
# 获得右边界
def getRightBorder(nums,target):
rightBorder=-2
lindex=0
rindex=len(nums)-1
while lindex<=rindex:
mid=lindex+(rindex-lindex)//2
if nums[mid] > target:
rindex=mid-1
else:
lindex=mid+1
rightBorder=lindex # 这里右边界更新
return rightBorder
# 获得左边界
def getLeftBorder(nums,target):
leftBorder=-2
lindex=0
rindex=len(nums)-1
while lindex<=rindex:
mid=lindex+(rindex-lindex)//2
if nums[mid] >= target:
rindex=mid-1
leftBorder=rindex # 这里左边界更新
else:
lindex=mid+1
return leftBorder
leftBorder = getLeftBorder(nums,target)
rightBorder = getRightBorder(nums,target)
# 情况一,target不在数组范围内时,以target在数组左侧为例,
# 二分查找会不断更新rindex的值,那么leftBorder不更新,一直为-2。同理可以推出,target在数组右侧的情况。
if leftBorder == -2 or rightBorder == -2:
return [-1,-1]
# 情况三,因为leftBorder和rightBorder分别位于target的前一个索引位置和后一个索引位置
# 故 rightBorder-leftBorder必定大于1
elif rightBorder-leftBorder > 1:
return [leftBorder+1,rightBorder-1]
# 情况二
else:
return [-1,-1]
参考
代码随想录-34. 在排序数组中查找元素的第一个和最后一个位置