Title
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 1:
Input: [1,3,5,6], 0 Output: 0
就是二分法的改造嘛，到最后就是right-value-left的模式，然后返回的直接就是left了
Solution
//cpp:
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int left = 0, right = nums.size() - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (nums[mid] == target) {
return mid;
}
else if (nums[mid] > target) {
right = mid - 1;
}
else {
left = mid + 1;
}
}
return left;
}
};
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
return lower_bound(nums.begin(), nums.end(), target) - nums.begin();
}
};