題目：

給一個按照非遞減順序排列的整數數組nums,和一個目標值target,請找出給定目標值在數組中的開始位置和結束位置。

如果數組中不存在目標值target,返回[-1,-1]

---

方法一：二分查找

直觀的思路肯定是從前往后遍歷一遍。用兩個變量記錄第一次和最后一次遇見?target?的下標，但這個方法的時間復雜度為?O(n)，沒有利用到數組升序排列的條件

由于數組已經排序，因此整個數組是單調遞增的，可以利用二分法來加速查找的過程。

考慮?target?開始和結束位置，要找的就是數組中「第一個等于?target?的位置」（記為?leftIdx）和「第一個大于?target?的位置減一」（記為?rightIdx）

二分查找中，尋找 leftIdx 即為在數組中尋找第一個大于等于 target 的下標，尋找 rightIdx 即為在數組中尋找第一個大于 target 的下標，然后將下標減一。兩者的判斷條件不同，定義binarySearch(nums, target, lower) 表示在 nums 數組中二分查找 target 的位置，如果 lower 為 true，則查找第一個大于等于 target 的下標，否則查找第一個大于 target 的下標。

因為 target 可能不存在數組中，因此需要重新校驗得到的兩個下標 leftIdx 和 rightIdx，看是否符合條件，如果符合條件就返回 [leftIdx,rightIdx]，不符合就返回 [?1,?1]

class Solution(object):def searchRange(self, nums, target):""":type nums: List[int]:type target: int:rtype: List[int]"""leftIdx=self.binarySearch(nums,target,True)#查找左邊界，第三個參數True表示查找左邊界rightIdx=self.binarySearch(nums,target,False)-1#第三個參數False表示查找右邊界,結果減1if leftIdx<=rightIdx and rightIdx<len(nums) and nums[leftIdx]== target and nums[rightIdx] == target:  #判斷范圍有效return [leftIdx,rightIdx]return [-1,-1]def binarySearch(self,nums,target,lower):#輸入有序數組，目標值，布爾值left=0  #初始化二分查找的左右指針right=len(nums)-1ans=len(nums) #初始化答案為數組長度(表示目標值可能插入的位置)while left<=right:mid=(left+right)//2  # 計算中間位置if nums[mid]>target or (lower and nums[mid]>=target):
#查找左邊界時(lower=True)，當nums[mid] >= target時移動右指針
#查找右邊界時(lower=False)，只有當nums[mid] > target時才移動右指針right=mid-1ans=mid  ## 更新答案為當前的 midelse:left=mid+1  ## 目標值大于 mid 的值，移動左邊界return ans

時間復雜度：?O(logn)?，其中?n?為數組的長度。二分查找的時間復雜度為?O(logn)，一共會執行兩次，因此總時間復雜度為?O(logn)

空間復雜度：O(1)

作者：力扣官方題解
?