A Binary-search based C++ solution with explanation


  • 0
    J

    First of all, this problem is equivalent to finding the index of first element in nums which does not compare less than the target, or to say, it is a lower bound problem.

    Suppose the index of nums is 0, 1, 2, ... , n

    The valid lower bound index is actually 0, 1, 2, ... , n, n+1 (Note the n+1 is inclusive). so we do initialization as below in the solution.

    int lower_bound(vector<int>& nums, int target) {
        // NOTE: range of index is [0, nums.size()]
        // the begin is the index of the possible lower bound
        size_t begin = 0, end = nums.size(), mid;
        while( begin < end ) {
            mid = (begin + end) / 2;
            if(nums[mid] >= target ) end = mid;
            else begin = mid+1;
        }
        return begin;
    }
    

    Every iteration, if nums[mid] >= target, move the end to mid.

    Since begin < end and we calculate mid by (begin + end) / 2, the mid will at least 1 smaller then end.

    If not, nums[mid] is less then target, so move begin 1 step after mid.


  • 0
    L
    class Solution {
    public:
        int searchInsert(vector<int>& nums, int target) {
            if(nums.empty())
                return 0;
            
            vector<int>::iterator iter = find(nums.begin(), nums.end(), target);
        
            if(iter != nums.end())
                return iter - nums.begin();
            else{
                for(iter = nums.begin(); iter != nums.end(); iter++){
                    if(*iter > target)
                        return iter - nums.begin();
                }
            }
            return nums.size();
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.