34. 在排序数组中查找元素的第一个和最后一个位置
题目来源：力扣（LeetCode）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]
解题思路
思路：二分查找
题目中说明，【算法时间复杂度必须是 O(log n) 级别】，而且题意说给定的数组是已经按照升序排列的。那么这里，我们考虑使用二分查找的方法来解决此问题。
在这里，如果没有上面的限制，可以使用线性的时间来解决问题。
具体实现过程：
- 先从左到右遍历数组，遇到第一个元素与 target 值相同时，记录索引，跳出循环，如果循环到结束还没有遇到有与 target 值相同的元素，那么直接返回
[-1, -1]。 - 第二次遍历，从右往左遍历，同样遇到第一个与
target值相等的元素，记录索引退出循环。 - 最终返回两个索引值。
以上就是在没有限制时间复杂度的去情况下，用线性时间解决问题的方案。代码部分建议可尝试编写，这里不再贴出。
下面主要说下，如何使用二分查找解决问题。
这里同样分两次去查找最左边和最右边的对应值的索引。这里需要注意的是，无论是找最左边或是最右边的元素索引，都不是找到与 target 值相同的元素索引就马上停止，因为元素会重复，第一个找到的可能并不是最左边或是最右边的元素。
这里需要注意的是，查找左右两边的元素时，需要注意的是边界的问题。这里利用 and 短路计算来引入一个变量 sign，处理边界问题。
当遇到元素值与 target 值相同时，如果 sign 为 True 时，这个时候应该搜索左边部分。如果当前元素值等于 target，那么最左边的元素索引不能大于当前元素索引，所以范围应该缩小在左边部分。同样，求最右边索引也是一样的道理。
具体的代码实现如下。
代码实现
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
def search_index(nums, target, sign):
left = 0
right = len(nums)
while left < right:
mid = (left+right) // 2
if nums[mid] > target or (sign and target==nums[mid]):
right = mid
else:
left = mid + 1
return left
left_index = search_index(nums, target, True)
# 这里提前判断下，检索的索引是否已经到达末尾
# 或者检索的索引对应值是否不是 target，
# 如果是上面的两种情况，直接返回 [-1, -1]
if left_index == len(nums) or nums[left_index] != target:
return [-1, -1]
right_index = search_index(nums, target, False) - 1
return [left_index, right_index]
实现结果
实现结果
