Python, O(logN), with clear explanation


  • 0

    I used a binary search, by 2 pointers, left and right. In every iteration, I through away half of the nums. So in the first loop I can find the first instance of the smallest larger number. then the rest is pretty straightforward ^8^ (first time writing a post~)

    class Solution(object):
        def searchInsert(self, nums, target):
            """
            :type nums: List[int]
            :type target: int
            :rtype: int
            """
    
            #first use binary search to find the closest larger number in the array
            #also we found the first instance of the closest larger number in this way!
            n = len(nums)
            l , r = 0, n-1
            while l<r:
                m = int((l+r)/2)
                if nums[m]<target: l=m+1
                else: r = m
    
            #whether we have found the number?
            if nums[l] == target:
                return l
    
    
            #in this case, the target should be added in the end, out of range
            if l == n-1 and nums[l]<target: 
                return l+1
            
            return l
    

  • 0
    M
    if nums[l] == target:
                return l
    

    Nice Solution! However, these lines are redundant. you can simply remove them.


  • 0
    S
    class Solution(object):
        def searchInsert(self, nums, target):
            """
            :type nums: List[int]
            :type target: int
            :rtype: int
            """
            return self.bsHelper(nums, target, 0, len(nums) -1)
        
        def bsHelper(self, nums, target, low, high):
            if low > high:
                return -1
            mid = (low + high) /2
            if nums[mid] == target:
                return mid
            elif nums[mid] > target: #Case when target is less than mid
                if mid == 0 or nums[mid-1] < target :
                    return mid
                else:
                    high =  mid -1
                    return self.bsHelper(nums, target, low, high)
            else: #Case when target is greater than mid
                if mid == len(nums) - 1 or nums[mid + 1] > target:
                    return mid + 1
                else:
                    low = mid + 1
                    return self.bsHelper(nums, target, low, high)

Log in to reply
 

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