给定一个按照升序排列的整数数组 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]
分析：
因为有序所以先用二分找到该元素，若找不到，则返回{-1,-1},若找到，则接着判断它的边界，这时我们可以用二分法分别找比target大的那个元素与比target小的元素的坐标，且这两个元素只能有一个，若能找到则目标区间就确定了；但是这两个元素在数组中可能是多个的，那怎么办？我们调整下数据，所有数据扩大10倍+5，target变为target*10+5,这时我们可以找target*10+4和target*10+6,因为这两个元素不存在，所以可以确定target的上下边界。二分查找，找左右边界用二分，在nums[m]==target时先不停，继续l=m+1,或者r=m-1,知道l>r，这样返回的m就上下边界code1:
/* 执行用时 :12 ms, 在所有 Go 提交中击败了87.18%的用户 内存消耗 :4.2 MB, 在所有 Go 提交中击败了22.79%的用户 */ func bs(nums []int,l,r,target int)(bool,int){ m:=(l+r)/2 for l<=r{ m=(l+r)/2 if nums[m]*10+5==target{ return true,m }else if nums[m]*10+5<target{ l=m+1 }else{ r=m-1 } } return false,m } func searchRange(nums []int, target int) []int { if ok,_:=bs(nums,0,len(nums)-1,target*10+5);!ok{ return []int{-1,-1} } _,l:=bs(nums,0,len(nums)-1,target*10+4) if nums[l]!=target{ l=l+1 } _,r:=bs(nums,0,len(nums)-1,target*10+6) if nums[r]!=target{ r=r-1 } return []int{l,r} }code2:
/* 执行用时 :16 ms, 在所有 Go 提交中击败了42.12%的用户 内存消耗 :4.1 MB, 在所有 Go 提交中击败了60.76%的用户 */ func bs(nums []int,l,r,target,flag int)(int){ m:=(l+r)/2 for l<r{ m=(l+r)/2 if nums[m]<target||(flag==1&&nums[m]==target){ l=m+1 }else{//这边包含nums[m]==target部分,所以这样求的是最左边的元素 r=m } } return r } func searchRange(nums []int, target int) []int { l:=bs(nums,0,len(nums)-1,target,0) r:=bs(nums,0,len(nums)-1,target,1) if len(nums)==0||nums[l]!=target {//没找到，或者数组为空 l=-1;r=-1 }else{ if nums[r]!=target{//过了 r=r-1 } } return []int{l,r} }