Easy

Search Insert Position

LAB

Given sorted nums and target, return the index if found or the insertion index if not found.

EXAMPLES

Example 1

Input
{
  "nums": [
    1,
    3,
    5,
    6
  ],
  "target": 5
}

Output
2

FUNCTION SHAPE

nums: intArraytarget: int→int

SOLUTION NOTE

No post-processing needed. Note right = len(nums) since target could be larger than all elements.

Reveal reference solution +

pythonREFERENCE

def searchInsert(self, nums: List[int], target: int) -> int:
    left, right = 0, len(nums)  # Note: right = len(nums)
    while left < right:
        mid = left + (right - left) // 2
        if nums[mid] >= target:
            right = mid
        else:
            left = mid + 1
    return left

TimeO(log n)

SpaceO(1)

Open on LeetCode ↗