解法1:
直接使用STL:
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
const int l = distance(nums.begin(), lower_bound(nums.begin(), nums.end(), target));
const int u = distance(nums.begin(), prev(upper_bound(nums.begin(), nums.end(), target)));
if(nums[l] != target)
return vector<int> {-1, -1};
else
return vector<int> {l, u};
}
};
解法2:
二分查找,分别找到第一个和最后一个数
class Solution {
public:
int lower_bound(vector<int> &nums, int target){
int first = 0, last = nums.size() - 1;
while(first <= last){
int mid = (first + last) / 2;
if(nums[mid] == target){
if(mid == first || nums[mid - 1] != target)
return mid;
else
last = mid - 1;
}
else if(nums[mid] > target)
last = mid - 1;
else
first = mid + 1;
}
return -1;
}
int upper_bound(vector<int> &nums, int target){
int first = 0, last = nums.size() - 1;
while(first <= last){
int mid = (first + last) / 2;
if(nums[mid] == target){
if(mid == last || nums[mid + 1] != target)
return mid;
else
first = mid + 1;
}
else if(nums[mid] > target)
last = mid - 1;
else
first = mid + 1;
}
return -1;
}
vector<int> searchRange(vector<int>& nums, int target) {
int l = lower_bound(nums, target);
int u = upper_bound(nums, target);
return vector<int> {l, u};
}
};
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int first = 0, last = nums.size() - 1;
while(first <= last){
int mid = (first + last) / 2;
if(nums[mid] == target)
return mid;
else if(nums[mid] > target){
if(mid > first && nums[mid - 1] < target)
return mid;
else
last = mid - 1;
}
else if(nums[mid] < target){
if(mid < last && nums[mid + 1] > target)
return mid + 1;
else
first = mid + 1;
}
}
if(first == nums.size())
return nums.size();
if(last == -1)
return 0;
}
};
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int m = matrix.size();
int n = matrix.front().size();
int first = 0, last = m * n - 1;
while(first <= last){
int mid = (first + last) / 2;
if(matrix[mid / n][mid % n] == target)
return true;
else if(matrix[mid / n][mid % n] > target)
last = mid - 1;
else
first = mid + 1;
}
return false;
}
};