35.Search Insert Position

Tags: easy Array

Link: https://leetcode.com/problems/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.

---

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

---

Answer:

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

        return nums.size();
    }
};

二分搜索优化

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int n = nums.size();
        if (n == 0 || target <= nums[0]) return 0;
        if (target > nums.back()) return n;

        int left = 0, right = n - 1;
        while (left < right) {
            int middle = left + ((right - left) >> 1);
            if (nums[middle] < target) left = middle + 1;
            else right = middle;
        }
        return left;
    }
};

应用标准库，这里采用lower_bound()和upper_bound()是等效的。

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int n = nums.size();
        if (n == 0 || target <= nums[0]) return 0;
        if (target > nums.back()) return n;

        return (lower_bound(nums.begin(), nums.end(), target) - nums.begin());
    }
};

因为lower_bound()返回的是迭代器，所以还要减去nums.begin()来获得下标的位置。