Search Insert Position

Difficulty: Easy | Acceptance: 51.20% | Paid: No Topics: Array, Binary Search

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.

• Examples
• Constraints
• Approach 1: Linear Scan
• Approach 2: Binary Search

Examples

Example 1:

Input: nums = [1,3,5,6], target = 5 Output: 2 Explanation: 5 exists in the array at index 2.

Example 2:

Input: nums = [1,3,5,6], target = 2 Output: 1 Explanation: 2 would be inserted at index 1 to maintain sorted order.

Example 3:

Input: nums = [1,3,5,6], target = 7 Output: 4 Explanation: 7 would be inserted at the end of the array.

Constraints

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

Linear Scan

Intuition Since the array is already sorted, we can iterate through it from the beginning. The first element that is greater than or equal to the target is the correct insertion position (or the match itself).

Steps

• Iterate through the array using a loop.
• For each element, check if it is greater than or equal to the target.
• If yes, return the current index.
• If the loop completes without finding such an element, the target is larger than all existing elements, so return the length of the array.

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)

Complexity

• Time: O(n)
• Space: O(1)
• Notes: Simple to implement, but does not meet the O(log n) requirement.

Binary Search

Intuition The array is sorted, which allows us to use Binary Search to discard half of the search space in each step. We are looking for the leftmost position where the target can be inserted to maintain order.

Steps

• Initialize two pointers: left at 0 and right at nums.length - 1.
• While left is less than or equal to right:
  • Calculate the middle index mid.
  • If nums[mid] equals the target, return mid.
  • If nums[mid] is less than the target, move the left pointer to mid + 1.
  • If nums[mid] is greater than the target, move the right pointer to mid - 1.
• If the loop finishes, left will be pointing to the correct insertion index.

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

Complexity

• Time: O(log n)
• Space: O(1)
• Notes: Optimal solution that meets the problem’s runtime requirement.