leetcode 35 Search Insert Position

Posted by kele on May 28, 2018

给出一个数组,给定一个数字,查找需要插入的位置,数组已排好序,瞬间想到二分搜索,然后判断位置就可以了,判断位置判断的有点失败…..

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

修改版

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

运行时间多了2ms,但玄学的问题无法解决的….