35. Search Insert Position

Given a sorted array of distinct integers 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

Example 1:

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

Example 2:

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

Example 3:

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

Constraints:

• 1 <= nums.length <= 10^4
• -10^4 <= nums[i] <= 10^4
• nums contains distinct values sorted in ascending order.
• -10^4 <= target <= 10^4

Approach

Solution

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

        while l <= r:
            m = (l + r) // 2
            if nums[m] == target:
                return m
            elif nums[m] < target:
                l = m + 1
            elif nums[m] > target:
                r = m - 1

        return (l + r) // 2 + 1

Explanation