35. Search Insert Position¶

Edited by Charles

Easy · Python · Array

Problem

Read the original problem on LeetCode.

The official page contains the problem statement, examples, and constraints.

Explanation, examples & other approaches

Core idea

Use Binary Search.

If target exists in the sorted array, return its index.

Original study notes follow, including intermediate snippets and earlier attempts.

Idea¶

Use Binary Search.

If target exists in the sorted array, return its index.

If target does not exist, return the position where it should be inserted so that the array remains sorted.

Binary Search¶

Initialize:

left, right = 0, len(nums) - 1

The current search interval is:

[left, right]

Calculate:

mid = (left + right) // 2

There are three cases.

Case 1: `nums[mid] == target`¶

We found the target:

return mid

Case 2: `nums[mid] > target`¶

Since the array is sorted, target must be on the left side of mid.

right = mid - 1

Case 3: `nums[mid] < target`¶

target must be on the right side of mid.

left = mid + 1

Why Return `left`?¶

If target does not exist, binary search eventually ends when:

left > right

At this point:

... elements < target | elements > target ...
                      ↑
                     left

left is exactly the position where target should be inserted.

Another way to understand it:

right | left
        ↑
   insertion position

During binary search:

if nums[mid] < target:
    left = mid + 1

left keeps moving past elements that are definitely smaller than target.

Therefore, when the search finishes, left is the first position where target can be inserted.

Example¶

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

Initially:

index    0   1   2   3
nums     1   3   5   6
         ↑           ↑
        left       right

Round 1¶

left = 0
right = 3
mid = 1

nums[mid] = 3

Since:

3 > 2

move right:

right = mid - 1 = 0

Round 2¶

left = 0
right = 0
mid = 0

nums[mid] = 1

Since:

1 < 2

move left:

left = mid + 1 = 1

Now:

right = 0
left = 1

Therefore:

1 | 3
  ↑
 left

2 should be inserted between 1 and 3, so:

return left  # 1

Boundary Cases¶

If target is smaller than every element:

nums = [1, 3, 5, 6]
target = 0

left = 0

Insert at the beginning.

If target is larger than every element:

nums = [1, 3, 5, 6]
target = 7

left = 4

Insert at the end.

Thus, return left naturally handles all insertion positions.

Complexity¶

Time Complexity:

O(log n)

The search interval is reduced by half after each iteration.

Space Complexity:

O(1)

Only a few variables are used.

Key Points¶

Binary search interval:

[left, right]

Update rules:

nums[mid] > target
→ target is on the left
→ right = mid - 1

nums[mid] < target
→ target is on the right
→ left = mid + 1

If the target is not found:

right | left
        ↑
   insertion position

Therefore:

return left

Key intuition: left keeps moving past elements that are definitely smaller than target. When binary search finishes, left is exactly where target should be inserted.

Study record

Field	Value
Attempts	1
Mastery	❚
The Latest Attempt	September 8, 2026

Python solution¶

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1
        mid = (left + right) // 2

        while left <= right:
            if nums[mid] == target:
                return mid

            if nums[mid] > target:
                right = mid - 1
            else:
                left = mid + 1

            mid = (left + right) // 2

        return left

Back to Bonus Array · All Algorithm notes