Leetcode 35. Search Insert Position

https://leetcode.com/problems/search-insert-position/

We can add target to the list and resort, the first index of target is just what we want. While this solution does not take the advantage of sorted array and is wasteful.

Another method is to use binary search again.

Solution 1:

# T:O(nlgn) S:O(1)
class Solution:
    # @param {integer[]} nums
    # @param {integer} target
    # @return {integer}
    def searchInsert(self, nums, target):
        nums.append(target)
        nums.sort()
        return nums.index(target)

Run Time: 64 ms

Solution 2:

# T:O(lgn) S:O(1)
class Solution:
    # @param A, a list of integers
    # @param target, an integer to be inserted
    # @return integer
    def searchInsert(self, A, target):
        low, high = 0, len(A) - 1
        
        while low <= high:
            mid = low + (high - low) / 2
            if A[mid] == target:
                return mid
            elif A[mid] < target:
                low = mid + 1
            else:
                high = mid - 1
        
        return low

Run Time: 44 ms