给定一个按照升序排列的整数数组 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]思路：
首先确定存不存在，所以用一次二分查找来判断。
找到之后再用第二次二分查找往左边找左边界，找到的条件是 已经找到下标为0了 或者 找到某个target，它的左边不是target。
同理进行第三次二分查找，找右边界，找到的条件是 已经找到len(nums) - 1了 或者 找到某个target，它的右边不是target。
class Solution(object): def searchRange(self, nums, target): """ :type nums: List[int] :type target: int :rtype: List[int] """ lo, hi = 0, len(nums) - 1 #找第一个target while(lo <= hi): mid = (lo + hi) // 2 if nums[mid] == target: break elif nums[mid] > target: hi = mid - 1 else: lo = mid + 1 if lo > hi: #不存在 return [-1, -1] midtarget = mid lo, hi = 0, mid leftpos = 0 while(lo <= hi): # print lo, hi if (hi >= 1 and nums[hi - 1] != target) or hi == 0: #找到左边界或者找到头了 leftpos = hi break mid = (lo + hi) // 2 if nums[mid] == target: hi = mid elif nums[mid] < target: lo = mid + 1 rightpos = 0 lo, hi = midtarget, len(nums) - 1 while(lo <= hi): if (lo <= len(nums) - 2 and nums[lo + 1] != target) or lo == len(nums) - 1: #找到右边界或者找到头了 rightpos = lo break mid = (lo + hi + 1) // 2 if nums[mid] == target: lo = mid elif nums[mid] > target: hi = mid - 1 return [leftpos, rightpos]
