Search Insert Position

Problem Id: 35 Difficulty: Easy Tag: Array Tag: Binary Search


Intuition

Just do a Binary Search. Use 2 index lo and hi, and always ensure that nums[lo] is smaller than target and nums[hi] is greater or equal to target.

Solution


class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        if not nums:
            return 0
        elif nums[-1] < target:
            return len(nums)
        elif nums[0] >= target:
            return 0

        lo, hi = 0, len(nums) - 1
        while hi - lo > 1:
            mid = (hi + lo) // 2
            if nums[mid] < target:
                lo = mid
            else:
                hi = mid

        return hi