題目

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

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

你必須設計并實現時間復雜度為?O(log n)?的算法解決此問題。

示例 1：

輸入：nums = [5,7,7,8,8,10], target = 8
輸出：[3,4]

示例?2：

輸入：nums = [5,7,7,8,8,10], target = 6
輸出：[-1,-1]

示例 3：

輸入：nums = [], target = 0
輸出：[-1,-1]

解析

問：如何理解 end = lowerBound(nums, target + 1) - 1 這段代碼？

答：要想找到 ≤target 的最后一個數，無需單獨再寫一個二分。我們可以先找到這個數的右邊相鄰數字，也就是 >target 的第一個數。在所有數都是整數的前提下，>target 等價于 ≥target+1，這樣就可以復用我們已經寫好的二分函數了，即 lowerBound(nums, target + 1)，算出這個數的下標后，將其減一，就得到 ≤target 的最后一個數的下標。

問：如果 ≥target+1 的第一個數不存在怎么辦？

答：這說明數組中的數都 ≤target。如果數組中有 target，那么數組的最后一個數（下標 n?1）就是 target（因為數組是遞增的）。同時，lowerBound(nums, target + 1) 在這種情況下會返回 n，減一得到 n?1，這正是我們要計算的下標。

問：為什么要寫 left + (right - left) / 2？

答：在面試或者實際場景中，你不一定知道輸入的數組有多長，萬一數組長度達到 int 最大值，left + right 可能會發生加法溢出。當然，如果只看本題的數據范圍，寫 (left + right) / 2 也可以。對于 Python 來說，由于沒有溢出這個概念，所以可以直接相加。

問：怎么判斷我寫的是哪一種二分？

答：看 while 循環的條件，如果是 left <= right，就是閉區間；如果是 left < right，就是半閉半開區間；如果是 left + 1 < right，就是開區間。

問：對于閉區間寫法，為什么 nums[mid] >= target 的時候要寫 right = mid - 1？此時的 mid 不是有可能是答案嗎？這樣寫不會錯過答案嗎？

答：答案在區間外面，不在區間里面。如果覺得答案在區間里面的話，請思考這個問題：閉區間循環結束后 left>right，區間 [left,right] 是空的，什么也沒有，難道答案在空區間里面嗎？

問：我看到一種二分的寫法，在二分的過程中，額外記錄答案的值，你對此怎么看？

答：喜歡這種寫法的同學，推薦寫開區間二分，因為開區間二分 if 條件成立時更新的是哪個變量，最后返回的也就是哪個變量。這和記錄答案的做法如出一轍。

問：關于開區間二分，如何理解 ?1 和 n 這兩個下標？

答：可以假設 nums[?1]=?∞ 以及 nums[n]=∞，此時 nums 仍然是有序的。在這種情況下，nums[?1]<target，所以 ?1 是紅色；nums[n]≥target，所以 n 是藍色。

作者：靈茶山艾府
鏈接：https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/solutions/1980196/er-fen-cha-zhao-zong-shi-xie-bu-dui-yi-g-t9l9/
來源：力扣（LeetCode）

答案

class Solution:# lower_bound 返回最小的滿足 nums[i] >= target 的下標 i# 如果數組為空，或者所有數都 < target，則返回 len(nums)# 要求 nums 是非遞減的，即 nums[i] <= nums[i + 1]def lower_bound(self, nums: List[int], target: int) -> int:left, right = -1, len(nums)  # 開區間 (left, right)while left + 1 < right:  # 區間不為空mid = (left + right) // 2# 循環不變量：# nums[left] < target# nums[right] >= targetif nums[mid] >= target:right = mid  # 范圍縮小到 (left, mid)else:left = mid  # 范圍縮小到 (mid, right)# 循環結束后 left+1 = right# 此時 nums[left] < target 而 nums[right] >= target# 所以 right 就是第一個 >= target 的元素下標return 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]  # nums 中沒有 target# 如果 start 存在，那么 end 必定存在end = self.lower_bound(nums, target + 1) - 1return [start, end]# 作者：靈茶山艾府
# 鏈接：https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/solutions/1980196/er-fen-cha-zhao-zong-shi-xie-bu-dui-yi-g-t9l9/
# 來源：力扣（LeetCode）

復雜度分析

時間復雜度：O(logn)，其中?n?為?nums?的長度。

空間復雜度：O(1)，僅用到若干額外變量。