Python编程题52--在排序列表中查元素的第⼀个和最后⼀个位
置
题⽬
给定⼀个按照升序排列的整数列表 nums，和⼀个⽬标值 target。请查出给定⽬标值在列表中的开始位置和结束位置。
如果列表中不存在⽬标值 target，则返回 [-1, -1]。
例如：
给定⼀个列表 nums ：[5, 7, 7, 8, 8, 10]，target = 8
返回结果：[3, 4]python index函数
给定⼀个列表 nums ：[5, 7, 7, 8, 8, 10]，target = 6
返回结果：[-1, -1]
给定⼀个列表 nums ：[]，target = 0
返回结果：[-1, -1]
实现思路1
定义2个变量：left_index、right_index ，分别表⽰开始位置和结束位置，默认值均为 -1
直接进⾏⼀轮遍历，如果列表中存在⽬标值 target，那么就记录第⼀个出现的位置，并更新到 left_index、right_index，如果在剩余列表元素中依然存在⽬标值 target，那么就只更新 right_index
代码实现
class Solution:
def search_range(self, nums, target):
left_index, right_index = -1, -1
for i, value in enumerate(nums):
if value == target and left_index == -1:
left_index = i
if value == target:
right_index = i
return [left_index, right_index]
时间复杂度：O(n)
空间复杂度：O(1)
实现思路2
使⽤⼆分查来实现
定义2个变量：left_index、right_index ，分别表⽰开始位置和结束位置，通过⼆分查判断，如果列表 nums 中不存在⽬标值 target，则直接返回 [-1, -1]，如果列表中存在⽬标值 target，并且查出来的⽬标值下标为 index ，那么就将 left_index、right_index 均更新为 index
在上⾯⼆分查时，因为列表中可能存在多个相同元素，所以查出来的 index 不⼀定是⽬标值 target 在列表中第⼀个出现的位置，因此需要对 left_index、right_index 做进⼀步处理
对于left_index，如果其左侧的元素也等于⽬标值，即nums[left_index - 1] == target，那么就连续更新 left_index = left_index - 1，直到 left_index 恰为⽬标值在列表中第⼀个出现的下标位置
对于right_index，如果其右侧的元素也等于⽬标值，即nums[right_index + 1] == target，那么就连续更新 right_index = right_index + 1，直到right_index 恰为⽬标值在列表中最后⼀个出现的下标位置
代码实现
class Solution:
def search_range(self, nums, target):
index = self.binary_search(nums, target)
if index == -1:  # 如果列表中不存在 target
return [-1, -1]
left_index, right_index = index, index
while left_index > 0 and nums[left_index - 1] == target:  # 处理 left_index，到第⼀个出现位置
left_index -= 1
while right_index < len(nums) - 1 and nums[right_index + 1] == target:  # 处理 right_index，到最后⼀个出现位置
right_index += 1
return [left_index, right_index]
def binary_search(self, nums, target):  # ⼆分查
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] > target:
right = mid - 1
elif nums[mid] < target:
left = mid + 1
else:
return mid
return -1
从上⾯可以看到，如果列表中可能存在多个相同元素，那么我们通过⼆分查法查返回的元素下标可能不是第⼀个出现位置，因此，我们可以对上⾯的⼆分查进⾏改进：
在⼆分查函数 binary_search() 的参数中增加⼀个参数：flag
如果flag为True，那么表⽰查列表nums中第⼀个⼤于等于target的下标
如果flag为False，那么表⽰查列表nums中第⼀个⼤于target的下标
优化后的代码如下：
class Solution:
def search_range(self, nums, target):
left_index = self.binary_search(nums, target, True)  # 查第⼀个⼤于等于target的索引
right_index = self.binary_search(nums, target, False)  # 查第⼀个⼤于target的索引
if left_index <= right_index - 1 and nums[left_index] == target and nums[right_index - 1] == target:
return [left_index, right_index - 1]
return [-1, -1]
def binary_search(self, nums, target, flag):  # 改进后的⼆分查
left, right, index = 0, len(nums) - 1, len(nums)
while left <= right:
mid = (left + right) // 2
if (nums[mid] > target) or (flag and nums[mid] >= target):
right = mid - 1
index = mid
else:
left = mid + 1
return index
时间复杂度：O(log n)
空间复杂度：O(1)
更多Python编程题，等你来挑战：