1只冻、題目描述
Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.
Your algorithm's runtime complexity must be in the order of O(log n).
If the target is not found in the array, return [-1, -1].
Example 1:
Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]
Example 2:
Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]
2难衰、問題描述：
- 給一個排好序的數(shù)組喳资，給一個target羡蛾，查找target起始位置衍腥，和最終位置盏缤。如果沒有绪穆，那么返回-1， -1.
3虱岂、問題關(guān)鍵：
- 有序玖院，一般二分查找，二分的兩個模版第岖，一個是求小于等于target的最大值难菌，一個是大于等于target的最小值。
- 一般寫二分的思考順序是這樣的：首先通過題目背景和check(mid)函數(shù)的邏輯蔑滓，判斷答案落在左半?yún)^(qū)間還是右半?yún)^(qū)間郊酒。
左右半?yún)^(qū)間的劃分方式一共有兩種： - 1.中點mid屬于左半?yún)^(qū)間遇绞，則左半?yún)^(qū)間是[l, mid]，右半?yún)^(qū)間是[mid+1, r]燎窘，更新方式是r = mid;或者 l = mid + 1;摹闽，此時用第一個模板；
- 2.中點mid屬于右半?yún)^(qū)間褐健，則左半?yún)^(qū)間是[l, mid-1]付鹿，右半?yún)^(qū)間是[mid, r]，更新方式是r = mid - 1;或者 l = mid;蚜迅，此時用第二個模板舵匾；
4、C++代碼：
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
if (nums.empty()) return vector<int>({-1, -1});
int n = nums.size();
vector<int> res;
int l = 0, r = n - 1;
while(l < r) {
int mid = l + r >> 1;//小于等于k的最大值谁不。（答案在左邊）
if (nums[mid] >= target) r = mid;
else l = mid + 1;
}
if (nums[l] != target) return vector<int>({-1, -1});//不存在這個數(shù)坐梯。
res.push_back(l);
l = 0, r = n - 1;
while(l < r) {
int mid = l + r + 1 >> 1;//大于等于target的最小值。（答案在右邊）
if (nums[mid] <= target) l = mid;
else r = mid - 1;
}
res.push_back(l);
return res;
}
};
