LeetCode 35 Search Insert Position（搜索并插入）

翻译

给定一个已排序的数组和一个目标值，如果这个目标值能够在数组中找到则返回索引。如果不能，返回它应该被插入的位置的索引。

你可以假设数组中没有重复项。

以下是一些示例。

原文

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.size() < 1) {
            return 0;
        } else if(nums.size() == 1) {
            if(nums[0] > target) return 0;
            else if(nums[0] == target) return 0;
            else return 1;
        } else {
            int flag = 0;   
            if (nums[0] > target) return 0;
            if(nums[nums.size() - 1] < target) return nums.size();
            for(int i = 0; i <= nums.size() - 1; ++ i) {
                if(nums[i] == target) return i;
                else if (nums[i] < target) flag = i;
                else {
                    if(flag == i - 1) return i;
                }
            }
        }
    }
};

在网上又看到这种了，分享给大家……

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