題目

34. 在排序數組中查找元素的第一個和最后一個位置 - 力扣（LeetCode）

思路

查找左邊界

初始化?left =?0,?right = nums.size() - 1

當?left?< right?時循環：

• 計算中點?mid =?left + (right?- left) /?2

• 如果?nums[mid]?< target，目標在右側，left = mid + 1

• 否則，目標在左側或當前位置，right =?mid

循環結束后，left ==?right，檢查?nums[left]?是否等于?target

查找右邊界

初始化?left?= 0,?right = nums.size() -?1

當?left?< right?時循環：

• 計算中點?mid = left?+ (right -?left +?1) /?2?（向上取整）

• 如果?nums[mid] > target，目標在左側，right?= mid -?1

• 否則，目標在右側或當前位置，left =?mid

循環結束后，left?== right，檢查?nums[left]?是否等于?target

圖解過程

以數組?[5,?7,?7, 8, 8,?10]，目標值?target?= 8?為例：

查找左邊界

初始狀態：

索引:  0  1  2  3  4  5
數組: [5, 7, 7, 8, 8, 10]↑           ↑left        right

?第一次迭代：

• mid =?0 + (5-0)/2 =?2

• nums[mid] = 7?< 8，目標在右側

• left?= mid +?1 =?3

索引:  0  1  2  3  4  5
數組: [5, 7, 7, 8, 8, 10]↑     ↑left  right

?第二次迭代：

• mid = 3?+ (5-3)/2?= 4

• nums[mid] =?8 ==?8，目標可能在左側

• right?= mid =?4

索引:  0  1  2  3  4  5
數組: [5, 7, 7, 8, 8, 10]↑  ↑left right

?第三次迭代：

• mid = 3?+ (4-3)/2?= 3

• nums[mid]?= 8?== 8，目標可能在左側

• right = mid = 3

索引:  0  1  2  3  4  5
數組: [5, 7, 7, 8, 8, 10]↑leftright

?循環結束：

• left?==?right =?3，循環結束

• nums[left] =?8 == target，找到左邊界?begin =?3

查找右邊界

初始狀態：

索引:  0  1  2  3  4  5
數組: [5, 7, 7, 8, 8, 10]↑           ↑left        right

?第一次迭代：

• mid = 0?+ (5-0+1)/2?= 3?（向上取整）

• nums[mid]?= 8?== 8，目標可能在右側

• left = mid =?3

索引:  0  1  2  3  4  5
數組: [5, 7, 7, 8, 8, 10]↑     ↑left  right

?第二次迭代：

• mid = 3?+ (5-3+1)/2 =?5?（向上取整）

• nums[mid] =?10?>?8，目標在左側

• right = mid -?1 =?4

索引:  0  1  2  3  4  5
數組: [5, 7, 7, 8, 8, 10]↑  ↑left right

?第三次迭代：

• mid = 3?+ (4-3+1)/2 =?4?（向上取整）

• nums[mid] =?8?== 8，目標可能在右側

• left?= mid =?4

索引:  0  1  2  3  4  5
數組: [5, 7, 7, 8, 8, 10]↑leftright

循環結束：

• left == right =?4，循環結束

• nums[left] =?8 ==?target，找到右邊界?end = 4

最終結果

返回?[begin, end]?= [3,?4]，表示目標值?8 的第一個位置是索引 3，最后一個位置是索引?4。

關鍵點

• 使用?left?< right?作為循環條件，確保循環結束時?left ==?right
• 查找左邊界時使用向下取整計算?mid，更新方式為?right?= mid
• 查找右邊界時使用向上取整計算 mid，更新方式為?left = mid
• 循環結束后檢查?nums[left]?是否等于目標值

讀者可能會出現的錯誤寫法

class Solution {
public:vector<int> searchRange(vector<int>& nums, int target) {if(nums.empty()){return {-1,-1};}int left = 0;int right = nums.size()-1;int begin = -1;int end =-1;while(left <= right){int mid = left + (right-left)/2;if(nums[mid]<target){left = mid + 1;}else{right = mid-1;}}if(nums[left] == target){begin = left;}left = 0;right = nums.size()-1;while(left <= right){int mid = left + (right-left)/2;if(nums[mid] > target){right = mid-1;}else{left = mid+1;}}if(nums[right] == target){end = right;}return {begin,end};}
};

在查找左邊界的時候，right = mid而不是right = mid-1;在查找右邊界的時候，left = mid而不是left = mid+1,并且left<right 而不是left<=right,并且當left=mid的條件下，mid = left + (right-left+1)/2,而不是mid = left + (right-left)/2

為什么要用right = mid而不是right = mid - 1？

• 如果nums[mid] == target，mid可能就是我們要找的左端點，或者左端點在mid左側

• 如果我們使用right =?mid - 1，就可能錯過正確答案

• 使用right =?mid可以保留mid作為可能的答案，同時繼續向左搜索

為什么我們使用right =?mid - 1，就可能錯過正確答案

假設數組中有多個相同的目標值，例如[1, 3, 3,?3, 5]，目標值target = 3。?

當我們找到一個nums[mid] == target時（例如中間的那個3），我們不知道這是不是第一個出現的3。有兩種可能：

• 當前找到的這個3就是第一個3
• 在mid左側還有其他的3

使用right = mid - 1的問題：

如果當前找到的nums[mid] == target恰好是第一個出現的目標值，那么使用right =?mid - 1會將搜索范圍縮小到mid左側，完全排除了mid這個位置。

具體例子：

• 數組[1, 2, 3,?4, 5]，target = 3

• 初始：left = 0,?right = 4

• 第一次迭代：mid = 2,?nums[mid] = 3 == target

• 如果使用right = mid - 1，區間變為[0, 1]

• 但索引2處的元素（值為3）是我們要找的答案！我們已經排除了它

• 后續迭代會在[0, 1]范圍內搜索，但這個范圍內沒有值為3的元素

• 最終會得出錯誤結論，認為數組中不存在目標值

使用right = mid的優勢：

當nums[mid]?== target時，使用right = mid：

• 將右邊界移動到mid（而不是mid-1）

• 保留了mid作為可能的答案

• 同時繼續在左側搜索是否有更早出現的目標值

這樣，即使當前的mid就是第一個目標值，我們也不會錯過它，因為：

• 如果左側沒有其他目標值，循環最終會收斂到這個位置

• 如果左側有目標值，我們會找到那個更早的位置

總結：使用right = mid - 1在找到目標值時會完全排除當前位置，如果當前位置恰好是第一個目標值，就會錯過正確答案。而right = mid保留了當前位置作為候選答案，同時繼續向左搜索可能存在的更早出現的目標值。

為啥查找左端點的mid算法和查找右端點的mid算法不一樣

考慮當搜索區間縮小到只有兩個元素時，例如?[3, 4]：

• left = 3, right = 4
• mid = 3 + (4-3)/2 =?3（向下取整）
• 如果?nums[mid] <=?target，執行?left = mid =?3
• 新的搜索區間仍然是?[3, 4]
• 下一次迭代，mid仍然是3
• 如果?nums[mid] <=?target，又執行?left = mid = 3
• 搜索區間永遠是?[3, 4]，無法進一步縮小，陷入死循環

使用向上取整的解決方案

使用向上取整?mid = left + (right -?left + 1) / 2?可以解決這個問題：

• left = 3, right = 4
• mid =?3 + (4-3+1)/2 = 4（向上取整）
• 如果?nums[mid] > target，執行?right?= mid - 1?= 3
• 搜索區間變為?[3, 3]，循環結束

或者，如果?nums[mid]?<= target，執行?left?= mid = 4，區間變為?[4, 4]，循環也會結束。

為什么查找左端點不需要向上取整

關鍵在于更新策略的不同：

查找左端點時：

• 當?nums[mid]?< target?時，使用?left?= mid +?1

• 這個?+1?確保了即使 mid?= left，區間也會縮小

查找右端點時：

• 當?nums[mid] <= target?時，使用?left = mid（沒有?+1）

• 如果 mid = left，區間不會縮小，導致死循環

總結

• 查找左端點時，即使使用向下取整，也不會導致死循環，因為：

• 當?nums[mid] < target?時，left = mid +?1?會縮小區間

• 當?nums[mid] >=?target?時，right?= mid?會縮小區間（因為 mid?≤ right）

• 查找右端點時，使用向下取整可能導致死循環，因為：

• 當?nums[mid] <=?target?且?mid = left 時，left = mid?不會縮小區間

當使用right = mid和left = mid這種更新方式時，循環條件應該是while(left < right)而不是while(left <= right)。為啥呀

原因如下：

主要原因：避免死循環

如果使用while(left <= right)作為循環條件，當left ==?right時循環仍會繼續執行：

當left == right時，無論使用什么mid計算方式，都會得到mid == left == right

此時：

• 如果執行right = mid，結果是right?= left，區間不變

• 如果執行left = mid，結果是left = right，區間不變

下一次循環，條件left <= right仍然滿足（因為left == right）

區間沒有縮小，算法陷入死循環

具體例子

假設數組[1, 3, 5]，當搜索區間縮小到[1, 1]（即left = right = 1）：

如果使用while(left <=?right)：

• mid = 1

• 如果執行right =?mid，區間仍為[1, 1]

• 如果執行left = mid，區間仍為[1, 1]

• 下一次循環，條件仍然滿足，陷入死循環

正確的寫法

class Solution {
public:vector<int> searchRange(vector<int>& nums, int target) {if(nums.empty()){return {-1,-1};}int left = 0;int right = nums.size()-1;int begin = -1;int end =-1;while(left < right){int mid = left + (right-left)/2;if(nums[mid]<target){left = mid + 1;}else{right = mid;}}if(nums[left] == target){begin = left;}left = 0;right = nums.size()-1;while(left < right){int mid = left + (right-left + 1)/2;if(nums[mid] > target){right = mid-1;}else{left = mid;}}if(nums[right] == target){end = right;}return {begin,end};}
};