0035. Search Insert Position

Easy | Array + Binary Search | 44 ms (91.85%), 15.2 MB (22.51%)

❓ Problem Statement

Source: LeetCode - Search Insert Position GitHub: Solution / Performance

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.

✍🏻 Constraints & Example

💡 Ideas

Binary Search Problem Sorted array to find a minimum index to insert target number in order.

Boundary / Search Space

Left (Minimum) = 0 Right (Maximum) = len(array) (last element could be the answer)

Condition

While Loop = Left < Right Return = array[mid] == target number

Return Value

Left (as index)

🤖 Python3

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        # (base case)
        if len(nums) == 1: return 0 if nums[0] >= target else 1
        
        # ==================================================
        #  Array + Binary Search                           =
        # ==================================================
        # time  : O(log(n))
        # space : O(1)
        
        l, r = 0, len(nums)
        while l < r:
            mid = (l + r) // 2
            
            if nums[mid] == target: return mid
            elif nums[mid] > target: r = mid
            elif nums[mid] < target: l = mid + 1
                
        return l

🤖 Java