给定一个按照升序排列的整数数组 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]
提示：
- 0 <= nums.length <= 10^5
- -10^9 <= nums[i] <= 10^9
- nums 是一个非递减数组
- -10^9 <= target <= 10^9
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
一解
使用二分搜索，当nums[mid] == target时：
- 循环查找 mid 左边的值 nums[mid - 1] 是否与 target 相同，最左边与 target 相同的值为答案中的起始位置。
- 循环查找 mid 右边的值 nums[mid + 1] 是否与 target 相同，最右边与 target 相同的值为答案中的结束位置。
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
l, r = 0, len(nums) - 1
start, end = -1, -1
while l <= r:
mid = l + (r - l)//2
if nums[mid] < target:
l = mid + 1
elif nums[mid] > target:
r = mid - 1
else:
while mid - 1 >= 0 and nums[mid-1] == target:
mid -= 1
start = mid
while mid + 1 < len(nums) and nums[mid + 1] == target:
mid += 1
end = mid
break
return start, end
- 时间复杂度 O(logn)：n 为数组长度。
- 空间复杂度 O(1)。
改进方案，可使用二次 binarySearch ，分别查找最左边 target （记为l）和最左边 target + 1 （记为 r），答案返回 [l, r-1]。
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
def binary_search(tar):
l, r = 0, len(nums) - 1
while l <= r:
mid = l + (r - l)//2
if nums[mid] < tar:
l = mid + 1
else:
r = mid - 1
return l
l = binary_search(target)
r = binary_search(target + 1)
if l == len(nums) or nums[l] != target:
return [-1, -1]
else:
return [l, r - 1]
- 时间复杂度 O(logn)：n 为数组长度。
- 空间复杂度 O(1)。