Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
You may assume no duplicates in the array.
Example 1:
Input: [1,3,5,6], 5 Output: 2
Example 2:
Input: [1,3,5,6], 2 Output: 1
Example 3:
Input: [1,3,5,6], 7 Output: 4
Example 4:
Input: [1,3,5,6], 0 Output: 0
已经排好序的数组，找出target或者target应该插入的位置。
显然二分查找，简单题，完整代码如下：
class Solution {
public:
int findPos(vector<int>& nums, int s, int t, int target)
{
if (s == t) {
if (nums[s] >= target)
return s;
else
return s + 1;
}
else if (s > t) { // caution!
return t + 1;
}
else {
int m = (s + t) / 2;
if (nums[m] == target)
return m;
else if (nums[m] > target)
return findPos(nums, s, m – 1, target);
else
return findPos(nums, m + 1, t, target);
}
}
int searchInsert(vector<int>& nums, int target) { return findPos(nums, 0, nums.size() – 1, target); }
};需要注意当s>t的分支，我也是遇到一个错误样例之后发现的。本代码提交AC，用时6MS。
本题也可以把递归改成非递归形式，而且好像不会有这种边界问题，代码如下：
class Solution {
public:
int searchInsert(vector<int>& nums, int target)
{
int l = 0, r = nums.size() – 1;
while (l <= r) {
int m = l + (r – l) / 2;
if (nums[m] == target)
return m;
if (nums[m] < target)
l = m + 1;
else
r = m – 1;
}
return l;
}
};本代码提交AC，用时9MS。