Search Insert Position

目录

• 题目链接
• 注意点
• 解法
• 小结

题目链接

Search Insert Position - LeetCode

注意点

• 输入的数组是有序的
• 有可能是要插入头或尾

解法

解法一：遍历数组找到两个数字 ——左边的小于target右边的大于target。时间复杂度为O(n)

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

解法二：二分查找，和查找数字略有不同，结束条件为left<right。时间复杂度为O(logn)

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

小结

• 二分查找