搜索插入位置

题目

搜索插入位置

 题目分析

1.第一个想法肯定是暴力遍历，找到了就输出下标，找不到就对比前后两个数字，寻找合适的位置插入。

2.需要注意一点，我们需要再一开始就对比target与数组最后一个数的大小，如果比数组最后一个数大，直接返回数组长度

3.第二个想法就是缩短寻找的时间，我们采用二分法，反复用数组中间的数与target比较，缩短数组长度。

二分法

代码

 代码一（暴力遍历）

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

代码二（二分法）

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