35. Search Insert Position

🟩 Easy

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,3,5,6], target = 5 Output: 2

Example 2

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

Example 3

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

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

Solution

My Solution

func searchInsert(nums []int, target int) int {
    l, r := 0, len(nums)-1

    for l <= r {
        mid := l + (r-l)/2
        if nums[mid] < target {
            l = mid + 1
        } else {
            r = mid - 1
        }
    }

    return l
}

Approach

This solution uses a modified binary search to find the insertion position:

1. Binary Search Implementation:

   • Uses standard binary search framework

   • When element is found, that's the insertion position

   • When element is not found, 'l' will be at the correct insertion position

2. Key Insights:

   • The left pointer 'l' always ends up at the correct insertion position

   • No need for special handling of not-found cases

   • Works for both existing and non-existing targets

Complexity Analysis

Time Complexity: O(log n)

• Uses standard binary search

• Search space is halved in each iteration

• Takes at most log₂(n) steps to find position

Space Complexity: O(1)

• Only uses constant extra space:

  • Two pointers (left, right)

  • Mid index variable

Why it works

• When target exists:

  • Binary search finds exact position

  • Left pointer stops at target's index

• When target doesn't exist:

  • Left pointer stops at first element greater than target

  • This is exactly where target should be inserted

  • Right pointer will be at left - 1

• Edge cases handled naturally:

  • Target smaller than all elements: left = 0

  • Target larger than all elements: left = len(nums)

result

Leetcode: link