題目描述
提示：
0 <= nums.length <= 105
-109 <= nums[i] <= 109
nums 是一個非遞減數組
-109 <= target <= 109
解題思路一
暴力解
頭到尾遍歷整個數組。
用一個變量 first 記錄第一次遇到 target 的索引。
繼續遍歷，用另一個變量 last 不斷更新最后一次遇到 target 的索引。
如果遍歷結束后 first 仍然是初始值（例如 -1），說明目標值不存在，返回 [-1, -1]。
否則，返回 [first, last]。
代碼實現：
/*** Note: The returned array must be malloced, assume caller calls free().*/
int* searchRange(int* nums, int numsSize, int target, int* returnSize) {int* result = (int*)malloc(sizeof(int) * 2);*returnSize = 2;int i = 0;int first = -1, last = -1;for (i = 0; i < numsSize; i++) {if (nums[i] == target) {first = i;break;}}if (first == -1) {result[0] = -1;result[1] = -1;return result;}for (i = first; i < numsSize; i++) {if (nums[i] == target) {last = i;}}result[0] = first;result[1] = last;return result;
}
執行結果：
class Solution {
public:vector<int> searchRange(vector<int>& nums, int target) {int first = -1,last=-1;for(int i=0;i<nums.size();++i){if(nums[i]==target){first = i;break;}}if(first==-1){return{-1,-1};}for(int i=nums.size()-1;i>=first;--i){if(nums[i]==target){last = i;break;}}return {first,last};}
};
復雜度分析：
時間復雜度：O(n)
空間復雜度：O（1）
解法二：二分查找
兩次二分查找是最優解
一次查找用于定位第一個等于 target 的位置（左邊界）。
另一次查找用于定位最后一個等于 target 的位置（右邊界）。
.1 查找左邊界（First Position）
我們需要修改二分查找的邏輯，使得當 nums[mid] == target 時，我們不立即返回，而是嘗試在左半部分繼續尋找，看看有沒有更靠前的 target。
具體步驟：
初始化 left = 0, right = n-1, first_pos = -1。
初始化 left = 0，right = n-1，first_pos = -1。
進入 while (left <= right) 循環。
輸入 while（left <= right） 循環。
計算 mid = left + (right - left) / 2。
計算 mid = left +（right - left）/ 2。
關鍵邏輯：
如果 nums[mid] > target，說明目標值在左側，right = mid - 1。
如果 nums[mid] < target，說明目標值在右側，left = mid + 1。
如果 nums[mid] == target，我們找到了一個 target。但它不一定是第一個。所以我們先將這個位置記錄下來 first_pos = mid，然后繼續在左半部分搜索，即 right = mid - 1，試圖找到一個更小的索引。
循環結束后，first_pos 中存儲的就是第一個目標值的位置。
2.2 查找右邊界（Last Position）
邏輯與查找左邊界非常相似，只是當找到 target 時，我們嘗試在右半部分繼續尋找。
具體步驟：
初始化 left = 0, right = n-1, last_pos = -1。
初始化 left = 0，right = n-1，last_pos = -1。
進入 while (left <= right) 循環。
輸入 while（left <= right） 循環。
計算 mid = left + (right - left) / 2。
計算 mid = left +（right - left）/ 2。
關鍵邏輯：
如果 nums[mid] > target，說明目標值在左側，right = mid - 1。
如果 nums[mid] < target，說明目標值在右側，left = mid + 1。
如果 nums[mid] == target，我們找到了一個 target。但它不一定是最后一個。所以我們先將這個位置記錄下來 last_pos = mid，然后繼續在右半部分搜索，即 left = mid + 1，試圖找到一個更大的索引。
循環結束后，last_pos 中存儲的就是最后一個目標值的位置。
最終：先執行查找左邊界的二分，如果沒找到（返回-1），直接返回 [-1, -1]。如果找到了，再執行查找右邊界的二分，最后將兩個結果組合成 [first_pos, last_pos] 返回。
代碼實現：
class Solution {
public:vector<int> searchRange(vector<int>& nums, int target) {int first_pos= -1, last_pos = -1;int left=0,right=nums.size()-1;while(left<=right){int mid = left+(right-left)/2;if(nums[mid]>target)right = mid-1;else if(nums[mid]<target)left=mid+1;else{first_pos=mid;right = mid-1;}}if(first_pos==-1)return {-1,-1};left = 0; right = nums.size() - 1;while(left<=right){int mid = left+(right-left)/2;if(nums[mid]>target)right = mid-1;else if(nums[mid]<target)left=mid+1;else{last_pos=mid;left = mid+1;}}return {first_pos,last_pos};}
};
執行結果
復雜度分析：
時間復雜度：O（logn）
空間復雜度：O（1）
優化在第二次while循環時，只在 [first_pos, n-1] 范圍內搜索而不是從【0，n-1】
思路三
巧用二分查找尋找邊界（思路二的變體）
這個思路更加巧妙，它將問題轉化為**“尋找第一個大于等于 target 的位置”** 和 “尋找第一個大于 target 的位置”。
尋找左邊界：
我們執行一次二分查找，目的是找到第一個大于或等于 target 的元素的索引。這個索引就是我們要的左邊界 left_bound。
這個查找過程也被稱為 lower_bound。
尋找右邊界：
我們再執行一次二分查找，目的是找到第一個大于 target 的元素的索引。
那么，這個索引減一，就是我們要的右邊界 right_bound。
這個查找過程也被稱為 upper_bound。
驗證結果：
在找到 left_bound 后，需要檢查一下 nums[left_bound] 是否真的等于 target。如果不是，或者 left_bound 越界了，說明 target 根本不存在，直接返回 [-1, -1]
#include <iostream>
#include <vector>class Solution {
public:std::vector<int> searchRange(std::vector<int>& nums, int target) {int first = -1;int last = -1;// 尋找第一個位置for (int i = 0; i < nums.size(); ++i) {if (nums[i] == target) {first = i;break; // 找到第一個就停止}}// 如果找不到，直接返回if (first == -1) {return {-1, -1};}// 尋找最后一個位置// 從后往前找會更高效for (int i = nums.size() - 1; i >= first; --i) {if (nums[i] == target) {last = i;break; // 找到第一個（從后往前看）就停止}}return {first, last};}
};
復雜度分析：
時間復雜度：O（logn）
空間復雜度：O（1）
ok,see you next time~
 訪問)
