在排序數組中查找元素的第一個和最后一個位置
作者：程序員Carl
給定一個按照升序排列的整數數組 nums，和一個目標值 target。找出給定目標值在數組中的開始位置和結束位置。
這個就是考察二分法的進階題目了
在排序數組中查找元素的第一個和最后一個位置
給定一個按照升序排列的整數數組 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]
思路
這道題目如果基礎不是很好，不建議大家看簡短的代碼，簡短的代碼隱藏了太多邏輯，結果就是稀里糊涂把題AC了，但是沒有想清楚具體細節!
對二分還不了解的同學先做這兩題：
- 704.二分查找
- 35.搜索插入位置
下面我來把所有情況都討論一下。
尋找target在數組里的左右邊界，有如下三種情況：
- 情況一：target 在數組范圍的右邊或者左邊，例如數組{3, 4, 5}，target為2或者數組{3, 4, 5},target為6，此時應該返回{-1, -1}
- 情況二：target 在數組范圍中，且數組中不存在target，例如數組{3,6,7},target為5，此時應該返回{-1, -1}
- 情況三：target 在數組范圍中，且數組中存在target，例如數組{3,6,7},target為6，此時應該返回{1, 1}
這三種情況都考慮到，說明就想的很清楚了。
接下來，在去尋找左邊界，和右邊界了。
采用二分法來去尋找左右邊界，為了讓代碼清晰，我分別寫兩個二分來尋找左邊界和右邊界。
剛剛接觸二分搜索的同學不建議上來就像如果用一個二分來查找左右邊界，很容易把自己繞進去，建議扎扎實實的寫兩個二分分別找左邊界和右邊界
尋找右邊界
先來尋找右邊界，至于二分查找，如果看過704.二分查找就會知道，二分查找中什么時候用while (left <= right)，有什么時候用while (left < right)，其實只要清楚循環不變量，很容易區分兩種寫法。
那么這里我采用while (left <= right)的寫法，區間定義為[left, right]，即左閉又閉的區間(如果這里有點看不懂了，強烈建議把704.二分查找這篇文章先看了，704題目做了之后再做這道題目就好很多了)
確定好：計算出來的右邊界是不包好target的右邊界，左邊界同理。
可以寫出如下代碼
- // 二分查找，尋找target的右邊界（不包括target）
- // 如果rightBorder為沒有被賦值（即target在數組范圍的左邊，例如數組[3,3]，target為2），為了處理情況一
- int getRightBorder(vector<int>& nums, int target) {
- int left = 0;
- int right = nums.size() - 1; // 定義target在左閉右閉的區間里，[left, right]
- int rightBorder = -2; // 記錄一下rightBorder沒有被賦值的情況
- while (left <= right) { // 當left==right，區間[left, right]依然有效
- int middle = left + ((right - left) / 2);// 防止溢出 等同于(left + right)/2
- if (nums[middle] > target) {
- right = middle - 1; // target 在左區間，所以[left, middle - 1]
- } else { // 當nums[middle] == target的時候，更新left，這樣才能得到target的右邊界
- left = middle + 1;
- rightBorder = left;
- }
- }
- return rightBorder;
- }
尋找左邊界
- // 二分查找，尋找target的左邊界leftBorder（不包括target）
- // 如果leftBorder沒有被賦值（即target在數組范圍的右邊，例如數組[3,3],target為4），為了處理情況一
- int getLeftBorder(vector<int>& nums, int target) {
- int left = 0;
- int right = nums.size() - 1; // 定義target在左閉右閉的區間里，[left, right]
- int leftBorder = -2; // 記錄一下leftBorder沒有被賦值的情況
- while (left <= right) {
- int middle = left + ((right - left) / 2);
- if (nums[middle] >= target) { // 尋找左邊界，就要在nums[middle] == target的時候更新right
- right = middle - 1;
- leftBorder = right;
- } else {
- left = middle + 1;
- }
- }
- return leftBorder;
- }
處理三種情況
左右邊界計算完之后，看一下主體代碼，這里把上面討論的三種情況，都覆蓋了
- class Solution {
- public:
- vector<int> searchRange(vector<int>& nums, int target) {
- int leftBorder = getLeftBorder(nums, target);
- int rightBorder = getRightBorder(nums, target);
- // 情況一
- if (leftBorder == -2 || rightBorder == -2) return {-1, -1};
- // 情況三
- if (rightBorder - leftBorder > 1) return {leftBorder + 1, rightBorder - 1};
- // 情況二
- return {-1, -1};
- }
- private:
- int getRightBorder(vector<int>& nums, int target) {
- int left = 0;
- int right = nums.size() - 1;
- int rightBorder = -2; // 記錄一下rightBorder沒有被賦值的情況
- while (left <= right) {
- int middle = left + ((right - left) / 2);
- if (nums[middle] > target) {
- right = middle - 1;
- } else { // 尋找右邊界，nums[middle] == target的時候更新left
- left = middle + 1;
- rightBorder = left;
- }
- }
- return rightBorder;
- }
- int getLeftBorder(vector<int>& nums, int target) {
- int left = 0;
- int right = nums.size() - 1;
- int leftBorder = -2; // 記錄一下leftBorder沒有被賦值的情況
- while (left <= right) {
- int middle = left + ((right - left) / 2);
- if (nums[middle] >= target) { // 尋找左邊界，nums[middle] == target的時候更新right
- right = middle - 1;
- leftBorder = right;
- } else {
- left = middle + 1;
- }
- }
- return leftBorder;
- }
- };
這份代碼在簡潔性很有大的優化空間，例如把尋找左右區間函數合并一起。
但拆開更清晰一些，而且把三種情況以及對應的處理邏輯完整的展現出來了。
總結
初學者建議大家一塊一塊的去分拆這道題目，正如本題解描述，想清楚三種情況之后，先專注于尋找右區間，然后專注于尋找左區間，左右根據左右區間做最后判斷。
不要上來就想如果一起尋找左右區間，搞著搞著就會顧此失彼，繞進去拔不出來了。
其他語言版本
Java
- class Solution {
- int[] searchRange(int[] nums, int target) {
- int leftBorder = getLeftBorder(nums, target);
- int rightBorder = getRightBorder(nums, target);
- // 情況一
- if (leftBorder == -2 || rightBorder == -2) return new int[]{-1, -1};
- // 情況三
- if (rightBorder - leftBorder > 1) return new int[]{leftBorder + 1, rightBorder - 1};
- // 情況二
- return new int[]{-1, -1};
- }
- int getRightBorder(int[] nums, int target) {
- int left = 0;
- int right = nums.length - 1;
- int rightBorder = -2; // 記錄一下rightBorder沒有被賦值的情況
- while (left <= right) {
- int middle = left + ((right - left) / 2);
- if (nums[middle] > target) {
- right = middle - 1;
- } else { // 尋找右邊界，nums[middle] == target的時候更新left
- left = middle + 1;
- rightBorder = left;
- }
- }
- return rightBorder;
- }
- int getLeftBorder(int[] nums, int target) {
- int left = 0;
- int right = nums.length - 1;
- int leftBorder = -2; // 記錄一下leftBorder沒有被賦值的情況
- while (left <= right) {
- int middle = left + ((right - left) / 2);
- if (nums[middle] >= target) { // 尋找左邊界，nums[middle] == target的時候更新right
- right = middle - 1;
- leftBorder = right;
- } else {
- left = middle + 1;
- }
- }
- return leftBorder;
- }
- }
- // 解法2
- // 1、首先，在 nums 數組中二分查找 target；
- // 2、如果二分查找失敗，則 binarySearch 返回 -1，表明 nums 中沒有 target。此時，searchRange 直接返回 {-1, -1}；
- // 3、如果二分查找成功，則 binarySearch 返回 nums 中值為 target 的一個下標。然后，通過左右滑動指針，來找到符合題意的區間
- class Solution {
- public int[] searchRange(int[] nums, int target) {
- int index = binarySearch(nums, target); // 二分查找
- if (index == -1) { // nums 中不存在 target，直接返回 {-1, -1}
- return new int[] {-1, -1}; // 匿名數組
- }
- // nums 中存在 targe，則左右滑動指針，來找到符合題意的區間
- int left = index;
- int right = index;
- // 向左滑動，找左邊界
- while (left - 1 >= 0 && nums[left - 1] == nums[index]) { // 防止數組越界。邏輯短路，兩個條件順序不能換
- left--;
- }
- // 向左滑動，找右邊界
- while (right + 1 < nums.length && nums[right + 1] == nums[index]) { // 防止數組越界。
- right++;
- }
- return new int[] {left, right};
- }
- /**
- * 二分查找
- * @param nums
- * @param target
- */
- public int binarySearch(int[] nums, int target) {
- int left = 0;
- int right = nums.length - 1; // 不變量：左閉右閉區間
- while (left <= right) { // 不變量：左閉右閉區間
- int mid = left + (right - left) / 2;
- if (nums[mid] == target) {
- return mid;
- } else if (nums[mid] < target) {
- left = mid + 1;
- } else {
- right = mid - 1; // 不變量：左閉右閉區間
- }
- }
- return -1; // 不存在
- }
- }
Python
- class Solution:
- def searchRange(self, nums: List[int], target: int) -> List[int]:
- def getRightBorder(nums:List[int], target:int) -> int:
- left, right = 0, len(nums)-1
- rightBoder = -2 # 記錄一下rightBorder沒有被賦值的情況
- while left <= right:
- middle = left + (right-left) // 2
- if nums[middle] > target:
- right = middle - 1
- else: # 尋找右邊界，nums[middle] == target的時候更新left
- left = middle + 1
- rightBoder = left
- return rightBoder
- def getLeftBorder(nums:List[int], target:int) -> int:
- left, right = 0, len(nums)-1
- leftBoder = -2 # 記錄一下leftBorder沒有被賦值的情況
- while left <= right:
- middle = left + (right-left) // 2
- if nums[middle] >= target: # 尋找左邊界，nums[middle] == target的時候更新right
- right = middle - 1;
- leftBoder = right;
- else:
- left = middle + 1
- return leftBoder
- leftBoder = getLeftBorder(nums, target)
- rightBoder = getRightBorder(nums, target)
- # 情況一
- if leftBoder == -2 or rightBoder == -2: return [-1, -1]
- # 情況三
- if rightBoder -leftBoder >1: return [leftBoder + 1, rightBoder - 1]
- # 情況二
- return [-1, -1]
- # 解法2
- # 1、首先，在 nums 數組中二分查找 target；
- # 2、如果二分查找失敗，則 binarySearch 返回 -1，表明 nums 中沒有 target。此時，searchRange 直接返回 {-1, -1}；
- # 3、如果二分查找成功，則 binarySearch 返回 nums 中值為 target 的一個下標。然后，通過左右滑動指針，來找到符合題意的區間
- class Solution:
- def searchRange(self, nums: List[int], target: int) -> List[int]:
- def binarySearch(nums:List[int], target:int) -> int:
- left, right = 0, len(nums)-1
- while left<=right: # 不變量：左閉右閉區間
- middle = left + (right-left) // 2
- if nums[middle] > target:
- right = middle - 1
- elif nums[middle] < target:
- left = middle + 1
- else:
- return middle
- return -1
- index = binarySearch(nums, target)
- if index == -1:return [-1, -1] # nums 中不存在 target，直接返回 {-1, -1}
- # nums 中存在 targe，則左右滑動指針，來找到符合題意的區間
- left, right = index, index
- # 向左滑動，找左邊界
- while left -1 >=0 and nums[left - 1] == target: left -=1
- # 向右滑動，找右邊界
- while right+1 < len(nums) and nums[right + 1] == target: right +=1
- return [left, right]
- # 解法3
- # 1、首先，在 nums 數組中二分查找得到第一個大于等于 target的下標（左邊界）與第一個大于target的下標（右邊界）；
- # 2、如果左邊界<= 右邊界，則返回 [左邊界, 右邊界]。否則返回[-1, -1]
- class Solution:
- def searchRange(self, nums: List[int], target: int) -> List[int]:
- def binarySearch(nums:List[int], target:int, lower:bool) -> int:
- left, right = 0, len(nums)-1
- ans = len(nums)
- while left<=right: # 不變量：左閉右閉區間
- middle = left + (right-left) //2
- # lower為True，執行前半部分，找到第一個大于等于 target的下標 ，否則找到第一個大于target的下標
- if nums[middle] > target or (lower and nums[middle] >= target):
- right = middle - 1
- ans = middle
- else:
- left = middle + 1
- return ans
- leftBorder = binarySearch(nums, target, True) # 搜索左邊界
- rightBorder = binarySearch(nums, target, False) -1 # 搜索右邊界
- if leftBorder<= rightBorder and rightBorder< len(nums) and nums[leftBorder] == target and nums[rightBorder] == target:
- return [leftBorder, rightBorder]
- return [-1, -1]
- # 解法4
- # 1、首先，在 nums 數組中二分查找得到第一個大于等于 target的下標leftBorder；
- # 2、在 nums 數組中二分查找得到第一個大于等于 target+1的下標， 減1則得到rightBorder；
- # 3、如果開始位置在數組的右邊或者不存在target，則返回[-1, -1] 。否則返回[leftBorder, rightBorder]
- class Solution:
- def searchRange(self, nums: List[int], target: int) -> List[int]:
- def binarySearch(nums:List[int], target:int) -> int:
- left, right = 0, len(nums)-1
- while left<=right: # 不變量：左閉右閉區間
- middle = left + (right-left) //2
- if nums[middle] >= target:
- right = middle - 1
- else:
- left = middle + 1
- return left # 若存在target，則返回第一個等于target的值
- leftBorder = binarySearch(nums, target) # 搜索左邊界
- rightBorder = binarySearch(nums, target+1) -1 # 搜索右邊界
- if leftBorder == len(nums) or nums[leftBorder]!= target: # 情況一和情況二
- return [-1, -1]
- return [leftBorder, rightBorder]
責任編輯：姜華
來源：
代碼隨想錄
