NUHMAN.com

Introduction

LeetCode 35: Search Insert Position is a classic binary search problem where you're asked to determine the index at which a target should be inserted into a sorted array, maintaining the order.

This problem strengthens your understanding of how binary search can be adapted for insertion points, not just for locating existing elements.

Problem Statement

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 inserted in order.

You must solve this with O(log n) time complexity.

Examples

go

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

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

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

Approach: Binary Search

You can use a standard binary search with a small tweak:

• If the target is found, return the index.
• If not found, the left pointer will end up at the correct insert position.

Go Implementation

go

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

    for left <= right {
        mid := left + (right-left)/2

        if nums[mid] == target {
            return mid
        } else if nums[mid] < target {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }

    return left // insert position
}

Example Walkthrough

go

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

Initial range: left = 0, right = 3
1. mid = 1 → nums[1] = 3 > target → right = 0
2. mid = 0 → nums[0] = 1 < target → left = 1

Loop ends, insert at index 1 ✅

Time and Space Complexity

MetricComplexityTime ComplexityO(log n)Space ComplexityO(1)

Efficient binary search ensures logarithmic time and constant space usage.

Edge Cases

• target is smaller than all elements → insert at index 0
• target is larger than all elements → insert at end (index = len(nums))
• Array contains only one element

Key Takeaways

• This problem demonstrates a very useful property: the left pointer will always point to the correct insert location after binary search terminates.
• A great example of how binary search can be adapted to solve more than just "find" problems.