[toc]

题目链接

Search Insert Position - LeetCode

注意点

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

解法

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

1class Solution {
2public:
3    int searchInsert(vector<int>& nums, int target) {
4        int i,n = nums.size();
5        for(i = 0;i < n-1;i++)
6        {
7            if(target > nums[i] && target <= nums[i+1])
8                return i+1;
9        }
10        if(target <= nums[0])
11        {
12            return 0;
13        }
14        if(target > nums[n-1])
15        {
16            return n;
17        }
18        return 0;
19    }
20};

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

1class Solution {
2public:
3    int searchInsert(vector<int>& nums, int target) {
4        int left = 0,right = nums.size()-1,middle;
5        if(target <= nums[0])
6        {
7            return 0;
8        }
9        if(target > nums[right])
10        {
11            return right+1;
12        }
13        while(left < right)
14        {
15            middle = (left+right)/2;
16            if(nums[middle] >= target)
17                right = middle;
18            else
19                left = middle+1;
20        }
21        return right;     
22    }
23};

小结

• 二分查找