题目描述
给你一个按照非递减顺序排列的整数数组 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]
解答
class Solution(object):def searchRange(self, nums, target):""":type nums: List[int]:type target: int:rtype: List[int]"""# # 思路一：二分查找法# # 特殊情况，直接返回 [-1, -1]# if not nums or target not in nums:# return [-1, -1]# # 获取数组的长度# n = len(nums)# # 初始化二分查找的左右边界# left, right = 0, n - 1# # 二分查找目标值# while left <= right:# # 计算中间元素的索引# mid = (left + right) // 2 # # 如果找到了目标值# if nums[mid] == target:# # 从中间位置开始，扩展查找最左边界和最右边界# l1, r1 = mid, mid# # 向左扩展，找到目标值的最左位置# while l1 > 0 and nums[l1 - 1] == target:# l1 -= 1# # 向右扩展，找到目标值的最右位置# while r1 < n - 1 and nums[r1 + 1] == target:# r1 += 1# # 返回最左和最右位置# return [l1, r1] # # 根据目标值与中间值的大小关系调整查找区间# if target < nums[mid]:# right = mid - 1 # 目标值小于中间值，向左查找# else:# left = mid + 1 # 目标值大于中间值，向右查找# # 如果没有找到目标值，返回 [-1, -1]# return [-1, -1]# 思路二：index法if not nums or target not in nums:return [-1, -1]# 获取数组的长度n=len(nums)left=nums.index(target)right=leftwhile right<n-1 and nums[right+1]==target:right+=1return [left,right]思路一：二分查找法
该方法通过二分查找在排序数组中找到目标值 target 的任意位置，然后从该位置向左右两侧扩展，分别查找目标值的最左端和最右端。这种方法的优势在于利用了二分查找的高效性，时间复杂度为 O(log n)，但扩展左右边界时会使用线性扫描，因此在某些情况下可能降低效率。
思路二：index 查找法
使用 Python 内建的 index() 方法找到目标值的第一个出现位置，然后通过向右扩展扫描，找出目标值的最右端位置。这种方法简洁直观，但它的时间复杂度较高，最坏情况下是 O(n)，尤其是在目标值出现多次时，因为需要对数组进行遍历。此方法适用于目标值较少重复的场景。
知识拓展：index方法
Python 中的 index() 方法用于查找一个元素在列表（或其他可迭代对象）中的 第一个 索引位置。如果该元素不存在，index() 会引发一个 ValueError 异常（这也是为什么在上一篇题解的代码中使用了 except ValueError）。它通常用于查找元素在列表中的索引，能够简化代码实现，但在某些场景下使用不当会导致性能问题。
1. 基本用法
index() 方法的基本语法如下：
list.index(element, start=0, end=len(list))element：要查找的元素。start（可选）：开始查找的位置，默认为 0。end（可选）：结束查找的位置，默认为列表的长度len(list)。
返回值是 元素在列表中第一次出现的索引，如果元素不在列表中，会引发 ValueError 异常。
2. 示例
# 示例 1：查找元素在列表中的索引
lst = [10, 20, 30, 40, 50]
index = lst.index(30)
print(index) # 输出: 2# 示例 2：指定 start 和 end 参数
index = lst.index(30, 2, 5) # 从索引 2 到 5 查找
print(index) # 输出: 2# 示例 3：元素不存在会抛出 ValueError
try:index = lst.index(100)
except ValueError:print("元素不存在")
3. 参数详解
element：查找目标元素。start：可选的查找起始位置，默认为 0，即从列表头部开始查找。如果指定了start，则会从指定的索引位置开始查找。end：可选的查找结束位置，默认为len(list)，即列表的末尾。如果指定了end，查找会限制在从start到end的范围内。
4. 性能分析
-
时间复杂度：
index()方法的时间复杂度是 O(n)，其中n是列表的长度。最坏情况下，index()需要遍历整个列表来找到目标元素。因此，当列表很大时，使用index()方法查找元素的效率较低，尤其在元素不存在或者出现在列表末尾时。 -
空间复杂度：O(1)，只需要常数空间。
5. 常见场景
-
查找元素的第一个出现位置：当你需要查找列表中某个元素第一次出现的位置时，
index()方法非常方便。 -
在已知元素存在的情况下：当你确定目标元素一定存在于列表中时，使用
index()方法能够快速得到元素的位置。 -
查找位置并作进一步处理：在一些情况下，我们希望知道一个元素在列表中的位置，以便后续处理。比如在排序数组中查找某个元素的位置。
6. index() 与 in 操作符
-
index()方法与in操作符的区别在于，in判断元素是否存在于列表中时，不会抛出异常，而index()查找元素时，如果元素不存在会引发ValueError异常。in操作符：用于检查元素是否在列表中，返回布尔值True或False。index()方法：返回元素的索引位置，如果元素不存在则抛出异常。
lst = [10, 20, 30]# 使用 'in' 判断元素是否存在
if 20 in lst:print("20 存在于列表中") # 输出: 20 存在于列表中# 使用 index() 查找元素的位置
try:index = lst.index(20)print("20 的索引位置:", index) # 输出: 20 的索引位置: 1
except ValueError:print("元素不存在")# 如果元素不存在，'in' 返回 False，而 index() 会抛出异常
if 40 in lst:print("40 存在于列表中")
else:print("40 不在列表中") # 输出: 40 不在列表中try:index = lst.index(40) # 抛出 ValueError
except ValueError:print("40 不在列表中") # 输出: 40 不在列表中
感谢阅读，希望对你有所帮助~
