34. 在排序數組中查找元素的第一個和最后一個位置

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

解法一：暴力查找

[1, 2, 3, 3, 3, 4, 5] t = 3
從前往后掃描暴力查找，最壞情況下O(N)

優化
利用數組有序的特性

解法二：樸素二分

[1, 2, 3, 3, 3, 4, 5] t = 3
?L? ? ? ? ? ?M ? ? ? ?R
在極端情況下時間復雜度會降低，比如如果數組內的元素都一樣

優化
[1, 2, 3, 3, 3, 4, 5] t = 3
[? ? ? ? ? ?] [ ? ? ? ? ? ?]
左邊區間小于t，右邊區間大于等于t

當發現問題中有二段線的規律時就可以用二分查找

?L ? ? ? ? ? ? M ? ? ? ? ? ? R
[-----------------------------] t
? ? ? ? ? ? ? ?x

查找區間左端點

1. x < t -> left = mid + 1 -> [left,right]

2. x >= t -> right = mid -> [left, right]?

因為 mid有可能是最終結果，所以不能更新到 mid + 1

細節處理：

1. 循環條件
left < right

a. 當 left = right的時候就是最終結果，無需判斷
b. 如果判斷，就會死循環

第一種情況：[left, right]中有結果
?L? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?R
[-----------------------------] t
[? ? ? ? ? ? ][ ? ? ? ? ? ? ? ? ? ?] ? ? ? ??
? ? ? ? ? ?t
因為 left = mid + 1，所以 left是想跳出左邊這個區域的
當left和right相遇的位置就是最終結果

第二種情況：全大于t
?L? ? ? ? ? ? ? ? ? ? ? ? ? ? ? R
[-----------------------------] t
只會命中第二個條件，right只會像左移動
直接判斷左端點的值是否是t

第三種情況：全小于t
只會命中第一個條件，left只會像右移動
直接判斷右端點的值是否是t

2. 求中點的操作
a. left + (right - left) / 2
b. left + (right - left + 1) / 2
當數組的個數是偶數時，用a求中點是靠左，用b是靠右

用b會陷入死循環，因為是右端點

當a。求的是左端點，當命中第一個條件時left會右移，此時相等的話就終止循環
當命中第二個條件時，right會更新到mid，此時兩個又相遇了，又終止循環了
所以求中點的操作只能用a才能終止循環

查找區間右端點

[1, 2, 3, 3, 3, 4, 5] t = 3
[? ? ? ? ? ? ? ? ? ? ][ ? ?]

左邊區間全部小于等于t，右邊全部大于t

?L ? ? ? ? ? ? M ? ? ? ? ? ? R
[-----------------------------] t
? ? ? ? ? ? ? ? x
1. x <= t，mid此時在左邊區域，所以更新left -> left = mid -> [left, right] left和right中繼續尋找結果

2. x > t，mid此時在右邊區域，更新right -> right = mid - 1 -> [left, right]

處理細節：
1. 循環條件
left < right

2. 求中點的方式
a. left + (right - left) / 2
b. left + (right - left + 1) / 2

b求的是右端點
當最后元素剩2個時
[* *]
?L R

如果使用a，那么mid現在落在L，那么對于第一個條件，left會在這里不動，然后mid又落在這個位置，就會陷入死循環
使用b，mid就在R，當命中第一個條件時，left會移動到right，終止循環
命中第二個條件，right移動到left，也會終止循環

代碼：C++

class Solution {
public:vector<int> searchRange(vector<int>& nums, int target) {// 處理邊界情況if(nums.size() == 0) return {-1, -1};int begin = 0;// 1. 二分左端點int left = 0, right = nums.size() - 1;while(left < right){int mid = left + (right - left) / 2; // 中點下標if(nums[mid] < target) left = mid + 1;else right = mid;}// 結束循環后，left和right相遇// 判斷是否有結果if(nums[left] != target) return {-1, -1};else begin = left; // 等于left或right都一樣，標記左端點// 2. 二分右端點// 其實left不需要重置，但是為了保持代碼的獨立性left = 0, right = nums.size() - 1;while(left < right){int mid = left + (right - left + 1) / 2; // 中點下標if(nums[mid] <= target) left = mid;else right = mid - 1;}return {begin, right}; // 此時left或者right都存的右端點}
};

當下面出現 -1 的時候，上面就 +1
分類討論的代碼，就題論題即可

查找區間左端點的模版

// 查找區間左端點的模版
while (left < right)
{int mid = left + (right - left) / 2;if (...) left = mid + 1;else right = mid;
}

?查找區間右端點的模版

// 查找區間右端點的模版
while (left < right)
{int mid = left + (right - left + 1) / 2;if (...) left = mid;else right = mid - 1;
}