[每日 LeetCode] 35. Search Insert Position

Description:

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
​

思路：题目要求查找有序数组中是否存在某个数字，如果存在则返回该位置，不存在则返回应该插入的位置。常规思路，从 i=0 依次遍历数组，如果 target 等于或者小于 i，则返回 i，如果 target 在 i 和 i+1 之间或遍历到了末尾，则返回 i+1。

C++ 代码

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

运行时间：9ms

运行内存：9.2M