LeetCode #35 Search Insert Position

Posted on | Post modified

Problem

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You may assume no duplicates in the array.

Examples

1
2
Input: [1,3,5,6], 5
Output: 2
1
2
Input: [1,3,5,6], 2
Output: 1
1
2
Input: [1,3,5,6], 7
Output: 4
1
2
Input: [1,3,5,6], 0
Output: 0

Solution1

Method: Brute Force

Time Complexity: O(n)

Space Complexity: O(1)

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def searchInsert(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        for idx, val in enumerate(nums):
            if target <= val:
                return idx
        
        return len(nums)

Solution2

Method: Binary Search

Time Complexity: O (log n)

Space Complexity: O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def searchInsert(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        low, high = 0, len(nums)

        while low < high:
            mid = (low + high)//2
            if nums[mid] >= target:
                high = mid
            else:
                low = mid + 1

        return low

or

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def searchInsert(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        low, high = 0, len(nums) - 1
        
        while low <= high:
            mid = low + (high - low) // 2
            if nums[mid] >= target:
                high = mid - 1
            else:
                low = mid + 1

        return low