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

int searchInsert(int* nums, int numsSize, int target)
{
    int pos = 0;
    for(int i = 0;i < numsSize;i++)
    {
        if(target == nums[i])
            return i;
        
        if(target > nums[i])
            pos += 1;
    }
    
    return pos;
}

2021.07.07更新
一种简洁的写法：

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int size = nums.size();
        for(int i = 0;i < size;i++)
        {
            if(nums[i] >= target) return i;
        }
        return size;
    }
};

运行效率:

执行用时：0 ms, 在所有 C++ 提交中击败了100.00%的用户
内存消耗：9.4 MB, 在所有 C++ 提交中击败了59.38%的用户

另一种解法是使用C++ STL中的low_bound:

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        return lower_bound(nums.begin(),nums.end(), target) - nums.begin();
    }
};

当然面试时面试官希望我们自己手动实现：

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int n = nums.size();
        int left = 0, right = n - 1,res = n;
        while(left <= right)
        {
            int mid = (right - left) / 2 + left;
            if(target <= nums[mid])
            {
                //记录上一次大于等于target的下标
                res = mid;
                right = mid - 1;
            }else{
                left = mid + 1;
            }   
        }
        return res;
    }
};

执行效率：

执行用时：4 ms, 在所有 C++ 提交中击败了88.52%的用户
内存消耗：9.4 MB, 在所有 C++ 提交中击败了58.09%的用户

更简洁的写法：

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int low = 0, high = nums.size()-1;

        // Invariant: the desired index is between [low, high+1]
        while (low <= high) {
            int mid = low + (high-low)/2;

            if (nums[mid] < target)
                low = mid+1;
            else
                high = mid-1;
        }
        return low;
    }
};

运行效率:

Runtime: 4 ms, faster than 82.54% of C++ online submissions for Search Insert Position.
Memory Usage: 9.6 MB, less than 52.61% of C++ online submissions for Search Insert Position.