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

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

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

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

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

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

Input: nums = [1], target = 0
Output: 0

💡 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

class Solution {
    /**
     * @time  : O(log(n))
     * @space : O(1)
     */
    
    public int searchInsert(int[] nums, int target) {
        /* base case */
        if(nums.length == 1) return (nums[0] >= target) ? 0 : 1;
        
        int l = 0, r = nums.length;
        while(l < r) {
            int mid = (l + r) / 2;
            
            if(nums[mid] == target) return mid;
            else if(nums[mid] > target) r = mid;
            else if(nums[mid] < target) l = mid + 1;
        }
        
        return l;
    }
}