標(biāo)簽： C++ 算法 LeetCode 數(shù)組 二分查找
每日算法——leetcode系列
問題 Search for a Range
Difficulty: Medium
Given a sorted array of integers, 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].For example,
Given[5, 7, 7, 8, 8, 10]and target value 8,
return[3, 4].
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
}
};
翻譯
搜索(目標(biāo)的)所在范圍
難度系數(shù)：中等
給定一個有序整數(shù)數(shù)組于购，找出給定值在其中的起始與結(jié)束索引袍睡。
算法的時間復(fù)雜度必須為O(logn)。
如果數(shù)組中沒有指定值肋僧，返回[-1, -1]斑胜。
例如控淡，給定[5, 7, 7, 8, 8, 10]，目標(biāo)值為8止潘，返回[3, 4]掺炭。
思路
對于有序數(shù)組， 查找可以用二分查找
由于有重復(fù)的值凭戴，如果二分法找到目標(biāo)涧狮，則分兩部分繼續(xù)二分查找
如果沒找到，返回[-1, -1]
代碼
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
int n = (int)nums.size();
int pos = binarySearch(nums, 0, n-1, target);
vector<int> result;
int low = -1, high = -1;
if (pos >= 0){
low = pos;
int l = low;
while (l >= 0) {
low = l;
l = binarySearch(nums, 0, low - 1, target);
}
high = pos;
int h = high;
while (h >= 0){
high = h;
h = binarySearch(nums, high + 1, n-1, target);
}
}
result.push_back(low);
result.push_back(high);
return result;
}
private:
int binarySearch(vector<int> nums, int low, int high, int target){
while (low <= high) {
int mid = low + (high - low)/2;
if (nums[mid] == target) {
return mid;
}
if (target > nums[mid]) {
low = mid + 1;
}
if (target < nums[mid]) {
high = mid - 1;
}
}
return -1;
}
};
