题目描述
给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。
你可以假设数组中无重复元素。
样例
示例 1:
输入: [1,3,5,6], 5
输出: 2
示例 2:
输入: [1,3,5,6], 2
输出: 1
示例 3:
输入: [1,3,5,6], 7
输出: 4
示例 4:
输入: [1,3,5,6], 0
输出: 0
算法1
考虑边界问题
C++ 代码
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
if(nums.empty())
{
nums.push_back(target);
return 0;
}
int l = 0, r = nums.size() - 1;
while(l < r)
{
int mid = l + r >> 1;
if(nums[mid] < target)
l = mid + 1;
else
r = mid;
}
if(nums[r] == target) // 发现
return r;
else if(nums[r] > target && r == 0) // 最左边
{
nums.insert(nums.begin(), target);
return 0;
}
else if(nums[r] < target && r == nums.size() - 1) // 最右边
{
nums.insert(nums.end(), target);
return nums.size() - 1;
}
else // 中间
{
nums.insert(nums.begin() + r - 1, target);
return r;
}
}
};