[toc]
题目链接
Search Insert Position - LeetCode
注意点
- 输入的数组是有序的
- 有可能是要插入头或尾
解法
解法一：遍历数组找到两个数字 ——左边的小于target右边的大于target。时间复杂度为O(n)
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int i,n = nums.size();
for(i = 0;i < n-1;i++)
{
if(target > nums[i] && target <= nums[i+1])
return i+1;
}
if(target <= nums[0])
{
return 0;
}
if(target > nums[n-1])
{
return n;
}
return 0;
}
};
解法二：二分查找，和查找数字略有不同，结束条件为left<right。时间复杂度为O(logn)
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int left = 0,right = nums.size()-1,middle;
if(target <= nums[0])
{
return 0;
}
if(target > nums[right])
{
return right+1;
}
while(left < right)
{
middle = (left+right)/2;
if(nums[middle] >= target)
right = middle;
else
left = middle+1;
}
return right;
}
};
