题目讲解:以35和34为例
class Solution {
private:
int target;
int bi_search(int left_index, int right_index, vector<int>& nums)
{
if (left_index >= right_index)
return right_index;
auto mid_index = ((right_index - left_index) >> 1) + left_index;
auto mid = nums[mid_index];
if (mid < target)
return bi_search(mid_index + 1, right_index, nums);
else if (mid > target)
return bi_search(left_index, mid_index - 1, nums);
return mid_index;
}
int check(vector<int>& candidates, vector<int>& nums)
{
auto size = nums.size();
int ans = -1;
for (auto& candidate : candidates) {
if (candidate >= 0 && candidate <= (size - 1)) {
if (nums[candidate] >= target)
ans = candidate;
}
}
return ans;
}
public:
int searchInsert(vector<int>& nums, int _target)
{
target = _target;
auto size = nums.size();
if (0 == size)
return 0;
if (1 == size) {
if (nums[0] >= target)
return 0;
else if (nums[0] < target)
return 1;
}
if (nums[0] >= target)
return 0;
if (nums[size - 1] < target)
return size;
auto mid_index = bi_search(0, size - 1, nums);
vector<int> candidates { mid_index + 1, mid_index, mid_index - 1 };
auto ans = check(candidates, nums);
return ans;
}
};
class Solution {
private:
int target;
int bi_search_lower(int left_index, int right_index, vector<int>& nums)
{
if (left_index >= right_index)
return right_index;
auto mid_index = ((right_index - left_index) >> 1) + left_index;
auto mid = nums[mid_index];
if (mid >= target)
return bi_search_lower(left_index, mid_index - 1, nums);
else
return bi_search_lower(mid_index + 1, right_index, nums);
}
int bi_search_upper(int left_index, int right_index, vector<int>& nums)
{
if (left_index >= right_index)
return right_index;
auto mid_index = ((right_index - left_index) >> 1) + left_index;
auto mid = nums[mid_index];
if (mid > target)
return bi_search_upper(left_index, mid_index - 1, nums);
else
return bi_search_upper(mid_index + 1, right_index, nums);
}
int check(vector<int>& candidates, vector<int>& nums)
{
auto size = nums.size();
int ans = -1;
for (auto& candidate : candidates) {
if (candidate >= 0 && candidate <= (size - 1)) {
if (nums[candidate] == target)
ans = candidate;
}
}
return ans;
}
public:
vector<int> searchRange(vector<int>& nums, int _target)
{
target = _target;
auto size = nums.size();
if (0 == size)
return { -1, -1 };
if (1 == size) {
if (nums[0] == target)
return { 0, 0 };
return { -1, -1 };
}
if (nums[0] > target)
return { -1, -1 };
if (nums[size - 1] < target)
return { -1, -1 };
auto mid_index = bi_search_lower(0, size - 1, nums);
vector<int> candidates = { mid_index + 1, mid_index, mid_index - 1 };
auto lower = check(candidates, nums);
if (-1 == lower)
return { -1, -1 };
mid_index = bi_search_upper(0, size - 1, nums);
candidates[0] = mid_index - 1;
candidates[1] = mid_index;
candidates[2] = mid_index + 1;
auto upper = check(candidates, nums);
if (-1 == upper)
return { -1, -1 };
return { lower, upper };
}
};