題目描述
給定一個(gè)按照升序排列的整數(shù)數(shù)組 nums，和一個(gè)目標(biāo)值 target。找出給定目標(biāo)值在數(shù)組中的開(kāi)始位置和結(jié)束位置。
如果數(shù)組中不存在目標(biāo)值 target刊头，返回 [-1, -1]。
時(shí)間復(fù)雜度為 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]
提示：
0 <= nums.length <= 105
-109 <= nums[i] <= 109
nums 是一個(gè)非遞減數(shù)組
-109 <= target <= 109
解題思路
直接遍歷數(shù)組原杂，找到第一次出現(xiàn)target和最后一次target的位置即可，沒(méi)找到直接返回[-1,-1]您机；但是時(shí)間復(fù)雜度為O(n)穿肄。
題目中是已經(jīng)升序排列的數(shù)組，利用這一特性际看，采用二分查找咸产，查找到第一個(gè)等于target的位置start，如果沒(méi)有仲闽，那么返回[-1,-1]脑溢，否則，再次二分查找赖欣，查找到第一個(gè)大于target的位置end屑彻，返回[start,end-1]验庙；時(shí)間復(fù)雜度為O(logn)。
也可以直接調(diào)用STL的二分查找函數(shù)社牲，lower_bound函數(shù)和upper_bound函數(shù)粪薛。
源碼
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
int n=nums.size();
int left=0,right=n;
while(left<right)
{
int mid=(right-left)/2+left;
if(nums[mid]<target)
{
left=mid+1;
}
else
{
right=mid;
}
}
if(left==n||nums[left]!=target)
{
return vector<int>{-1,-1};
}
int start=left;
left=0;right=n;
while(left<right)
{
int mid=(right-left)/2+left;
if(nums[mid]<=target)
{
left=mid+1;
}
else
{
right=mid;
}
}
int end=left-1;
vector<int>ans;
{
ans.push_back(start);
ans.push_back(end);
}
return ans;
/*
vector<int>ans{-1,-1};
if(!binary_search(nums.begin(),nums.end(),target))return ans;
ans[0]=lower_bound(nums.begin(),nums.end(),target)-nums.begin();
ans[1]=upper_bound(nums.begin(),nums.end(),target)-nums.begin()-1;
return ans;
*/
}
};
題目來(lái)源
來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)搏恤，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處违寿。
