Search Insert Position

Problem

• 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.

Python Solution

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

        while low <= high:
            mid = (high + low) // 2
            if nums[mid] == target:
                return mid

            if nums[mid] < target:
                low = mid + 1
            else: 
                high = mid - 1
        
        return low

Performance

• Runtime beats: 100%
• Memory beats: 25%

Complexity

• Time: O(log n)
• Space: O(log n)