Leetcode 35. Search Insert Position

Problem

Leetcode 35 - Search Insert Position

Example:

Input: nums = [1,3,5,6], target = 5
Output: 2

Input: nums = [1,3,5,6], target = 2
Output: 1

Input: nums = [1,3,5,6], target = 7
Output: 4

Approach

We can use the exact principle we used for normal Binary search.

Note that we must run the while loop left <= right instead of left < right

Once we finish the while loop, we can just return left which will return the index of where target should be when appended.

Visualization of the Approach:

nums = [1,3,5,6], target = 2
        l     r
nums[mid] = 5

nums = [1,3,5,6], target = 2
        l r
nums[mid] = 1

nums = [1,3,5,6], target = 2
          l
          r
nums[mid] = 3

nums = [1,3,5,6], target = 2
        r l

Since right < left, break loop

return left = 1

Here is the Python code for the solution:

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums)-1

        while left <= right:
            mid = (left+right) // 2

            if target < nums[mid]:
                left = mid+1
            elif target > nums[mid]:
                right = mid-1
            else:
                return mid
        
        return left    

Time Complexity and Space Complexity

Time Complexity: $O(log n)$

Space Complexity: $O(1)$