34. 在排序數組中查找元素的第一個和最后一個位置
一、算法邏輯（逐步通順講解每一步思路）
該算法用于在一個升序排列的數組 nums 中查找某個目標值 target 的第一個出現的位置和最后一個出現的位置。
? 1?? 定義 lower_bound 函數
def lower_bound(self, nums: List[int], target: int) -> int:left, right = -1, len(nums)while left + 1 < right:mid = (left + right) // 2if nums[mid] >= target:right = midelse:left = midreturn right- 這個函數返回的是第一個大于等于 target 的索引位置。
- 使用的是左閉右開區間?
[left+1, right)?的二分寫法，可以避免邊界處理錯誤。 - 循環終止時，
right?就是第一個滿足?nums[right] >= target?的位置。
? 2?? 查找目標值的起始位置
start = self.lower_bound(nums, target)- 如果?
nums[start] != target?或者?start == len(nums)，說明數組中不存在該元素，直接返回?[-1, -1]。
? 3?? 查找目標值的結束位置
end = self.lower_bound(nums, target + 1) - 1- 我們通過查找?
target + 1?的第一個位置，再減 1，就得到了?target?的最后一個位置。 - 因為數組是有序的，所以?
target + 1?第一次出現之前的所有元素都是?target。
? 4?? 返回結果
return [start, end]二、核心點總結
? 利用兩次二分查找精準定位范圍
- 使用兩次「lower_bound」分別找到起始位置和結束位置，避免了線性掃描，效率高。
? 巧妙的“target + 1”技巧
- 不需要額外編寫一個 upper_bound 函數，只需將目標值加一，即可復用 lower_bound 找出右邊界。
? 適合面試高頻題型
- 本題是典型的二分查找變形題，考察對邊界條件的理解和對二分思想的靈活運用。
? 可擴展性強
- 此種思路也可推廣到其他變種問題，如：統計某數字在排序數組中出現的次數（劍指 Offer 題）等。
class Solution:def lower_bound(self, nums:List[int], target:int)-> int:left, right = -1, len(nums)while left+1 < right:mid = (left+right)//2if nums[mid]>=target:right = midelse:left = midreturn rightdef searchRange(self, nums: List[int], target: int) -> List[int]:start = self.lower_bound(nums, target)if start==len(nums) or nums[start] != target:return [-1,-1]end = self.lower_bound(nums, target+1)-1return [start, end]三、時間復雜度分析
? 每次調用 lower_bound 是一個標準的二分查找過程：
- 時間復雜度為 O(log n)
? 整體算法執行了兩次二分查找：
- 總體時間復雜度為?O(log n)
四、空間復雜度分析
? 整個過程中沒有使用任何額外的數據結構：
- 所有變量都是常數級的局部變量
? 空間復雜度為 O(1)
? 總結一句話
這段算法通過兩次二分查找定位目標值的起始與結束位置，巧妙利用 target + 1 技巧避免重復編寫 upper_bound，具有高效、簡潔、穩定的特點，是解決有序數組中查找范圍類問題的經典解法之一，非常適合作為面試準備的重點內容。
)
