题目

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.

Here are few examples.
[1,3,5,6], 5 → 2
[1,3,5,6], 2 → 1
[1,3,5,6], 7 → 4
[1,3,5,6], 0 → 0

分析

这是上一题的子问题，直接拿过来稍微改改就行了。

实现

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        if(nums.empty()) return 0;
        int start=0, end=nums.size()-1;
        while(start<end){
            int mid = (start + end) / 2;
            if(nums[mid]>=target)
                end = mid;
            else
                start = mid+1;
        }
        if(nums[start]>=target) return start;
        return start+1;
    }
};

思考

题目顺序很不科学，感觉可以开始分类做了。