打卡群刷题总结0630——在排序数组中查找元素的第一个和最后一个位置
打卡群刷题总结0630——在排序数组中查找元素的第一个和最后一个位置
题目：34. 在排序数组中查找元素的第一个和最后一个位置
链接：https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array
给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。 你的算法时间复杂度必须是 O(log n) 级别。 如果数组中不存在目标值，返回 [-1, -1]。 示例 1: 输入: nums = [5,7,7,8,8,10], target = 8 输出: [3,4] 示例 2: 输入: nums = [5,7,7,8,8,10], target = 6 输出: [-1,-1]
解题：
1、二分查找变形题，套用模板即可。
二分查找标准模板：
针对二分查找的变形题，只用改变两个红框。
第一个红框的可选项为<和<=；
第二个红框的可选项为l和r。
当第一个红框为<=时，由于nums[mid] <= target，l就后移，那么循环结束后，nums[l] > target；同理可以得到nums[r] <= target；合起来为：nums[r] <= target < nums[l]。
当第一个红框为<时，循环结束后，nums[r] < target <= nums[l]。
那么来了，对于二分查找变形体，直接用模板就行了：
1）查找第一个等于target的数，我们使得循环结束后nums[r] < target <= nums[l]，那么第一个红框填<，第二个红框填l（一定存在解的前提）；
2）查找第一个大于target的数，我们使得循环结束后nums[r] <= target < nums[l]，那么第一个红框填<=，第二个红框填l；
3）查找最后一个小于target的数，我们使得循环结束后nums[r] < target <= nums[l]，第一个红框填<，第二个红框填r；
……
代码：
class Solution(object):
def searchRange(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
if len(nums) == 0:
return [-1, -1]
res = [-1, -1]
# 结束后，nums[r] <= target < nums[l]
l, r = 0, len(nums) - 1
while l <= r:
mid = (l + r) // 2
if nums[mid] <= target:
l = mid + 1
else:
r = mid - 1
# 不存在
if nums[r] != target:
return res
else:
res[1] = r
l = 0
# 结束后，nums[r] < target <= nums[l]
while l <= r:
mid = (l + r) // 2
if nums[mid] < target:
l = mid + 1
else:
r = mid - 1
res[0] = l
return res腾讯云开发者
