35.Search_Insert_Position_(Easy).md

35. Search Insert Position (Easy)

Date and Time: Jun 25, 2024, 16:27 (EST)

Link: https://leetcode.com/problems/search-insert-position/

Question:

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.

You must write an algorithm with O(log n) runtime complexity.

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

Custom:

Input: [1, 3, 5, 6], target = 0

Output: 0

KeyPoints:

This question is extremely similar to 704. Binary Search except that we add a new requirement that return the index where the target should be inserted if the target is not found. So, the approach is mostly identical to "Binary Search", but in the last four lines, we check two cases when the target is not found and is lower than nums or target is higher than nums.

For the custom edge case, if we insert the target 0: [0, 1, 3, 5, 6], and when the while loop ends, l = 0, r = -1, so we should return l or r + 1.

My 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:
                l = m + 1
            elif nums[m] > target:
                r = m - 1
            else:
                return m
        if nums[r] < target:
            return r + 1
        if nums[r] > target:
            return l

Time Complexity: $O(log\ n)$
Space Complexity: $O(1)$