Leetcode34.在排序数组中查找元素的第一个和最后一个位置

34. 在排序数组中查找元素的第一个和最后一个位置

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

示例 1：

1
2
>输入：nums = [5,7,7,8,8,10], target = 8
>输出：[3,4]

示例 2：

1
2
>输入：nums = [5,7,7,8,8,10], target = 6
>输出：[-1,-1]

示例 3：

1
2
>输入：nums = [], target = 0
>输出：[-1,-1]

基本思路也很简单，主要就是通过两次查询分别找到首尾的位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution(object):
    def searchRange(self, nums, target):
        if not nums:
            return [-1,-1]
        n = len(nums)

        def find(is_find_first):
			begin,end = 0, n-1
			while begin<=end:
                # step1: 首先找到元素的位置
				mid = begin+(end-begin)//2
				if nums[mid]>target:
					end = mid-1
				elif nums[mid]<target:
					begin = mid+1
				# step2: 开始确定元素存在的位置区间
				else:
					# 查找第一个和最后一个逻辑很类似，这里用一个变量标记
					# 输入True代表查找第一个，输入False代表查找最后一个
					if is_find_first:
                        # 输入True查找左边界
						# 如果不满足条件，缩小右边界，继续往左边查找
						if mid>0 and nums[mid]==nums[mid-1]:
							end = mid-1
						else:
							return mid
					else:
                        # 输入False查找右边界
						# 如果不满足条件，增大左边界，继续往右边查找
						if mid<n-1 and nums[mid]==nums[mid+1]:
							begin = mid+1
						else:
							return mid
			return -1
        return [find(True), find(False)]