35. Search Insert Position - Explanation

Problem Link

Description

You are 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,0,2,4,6,8], target = 5

Output: 4

Example 2:

Input: nums = [-1,0,2,4,6,8], target = 10

Output: 6

Constraints:

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


Company Tags

Please upgrade to NeetCode Pro to view company tags.



class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        for i in range(len(nums)):
            if nums[i] >= target:
                return i
        return len(nums)

Time & Space Complexity

  • Time complexity: O(n)O(n)
  • Space complexity: O(1)O(1) extra space.

2. Binary Search - I

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        res = len(nums)
        l, r = 0, len(nums) - 1
        while l <= r:
            mid = (l + r) // 2
            if nums[mid] == target:
                return mid
            if nums[mid] > target:
                res = mid
                r = mid - 1
            else:
                l = mid + 1
        return res

Time & Space Complexity

  • Time complexity: O(log⁡n)O(\log n)
  • Space complexity: O(1)O(1) extra space.

3. Binary Search - II

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        l, r = 0, len(nums) - 1
        while l <= r:
            mid = (l + r) // 2
            if nums[mid] == target:
                return mid
            if nums[mid] > target:
                r = mid - 1
            else:
                l = mid + 1
        return l

Time & Space Complexity

  • Time complexity: O(log⁡n)O(\log n)
  • Space complexity: O(1)O(1) extra space.

4. Binary Search (Lower Bound)

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        l, r = 0, len(nums)
        while l < r:
            m = l + ((r - l) // 2)
            if nums[m] >= target:
                r = m
            elif nums[m] < target:
                l = m + 1
        return l

Time & Space Complexity

  • Time complexity: O(log⁡n)O(\log n)
  • Space complexity: O(1)O(1)

5. Built-In Binary Search Function

import bisect
class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        return bisect.bisect_left(nums, target)

Time & Space Complexity

  • Time complexity: O(log⁡n)O(\log n)
  • Space complexity: O(1)O(1)