LeetCode 35 - Search Insert Position

The problem gives us a sorted array of distinct integers and a target value. Our task is to determine where the target belongs in the array. If the target already exists, we return its index.

leetcodeeasyarraybinary-search

LeetCode Problem 35

Difficulty: 🟢 Easy
Topics: Array, Binary Search

Solution

Problem Understanding

The problem gives us a sorted array of distinct integers and a target value. Our task is to determine where the target belongs in the array. If the target already exists, we return its index. If the target does not exist, we return the position where it should be inserted so that the array remains sorted.

The input consists of two parts. The first input, nums, is an array sorted in ascending order with no duplicate values. The second input, target, is the integer we want to search for. The expected output is a single integer representing either the existing index of the target or the insertion position that would preserve sorted order.

The important detail in this problem is the runtime requirement. The problem explicitly requires an O(log n) solution. This immediately rules out any linear scan approach for the optimal solution because iterating through the array from left to right would take O(n) time in the worst case.

The constraints also tell us several useful things:

  • The array length is at least 1, so we never deal with an empty array.
  • The array is sorted in ascending order, which strongly suggests binary search.
  • All values are distinct, so we never need to handle duplicate insertion ambiguity.
  • The values are relatively small, but the magnitude of values does not matter much because binary search depends on ordering, not value size.

Several edge cases are important to recognize early:

  • The target may be smaller than every element in the array, meaning the answer should be index 0.
  • The target may be larger than every element, meaning the answer should be len(nums).
  • The target may already exist in the array.
  • The target may fit somewhere in the middle between two elements.

A naive implementation can easily make off by one mistakes near the boundaries, especially when determining the insertion position after the binary search finishes.

Approaches

Brute Force Approach

The most straightforward solution is to scan the array from left to right. For each element, we compare it with the target.

If we find an element equal to the target, we return its index immediately. If we encounter an element greater than the target, we know the target should be inserted before it, so we return that index. If we finish iterating through the entire array without finding a larger value, the target belongs at the end of the array.

This approach works because the array is sorted. The first element that is greater than or equal to the target determines the correct insertion position.

However, this method is too slow for the problem requirements because it may examine every element in the array. Its worst case runtime is O(n), while the problem explicitly requires O(log n) complexity.

Optimal Approach

The key observation is that the array is already sorted. Whenever we have a sorted array and need logarithmic search performance, binary search becomes the natural solution.

Binary search repeatedly divides the search space in half. Instead of checking every element one by one, we inspect the middle element:

  • If the middle element equals the target, we return its index.
  • If the middle element is smaller than the target, we know the target must be on the right side.
  • If the middle element is larger than the target, we know the target must be on the left side.

Eventually, the search space becomes empty. At that point, the left boundary represents the correct insertion position.

The important insight is that binary search not only finds existing elements efficiently, it also naturally identifies where a missing element belongs.

Approach Time Complexity Space Complexity Notes
Brute Force O(n) O(1) Scans the array sequentially until the correct position is found
Optimal O(log n) O(1) Uses binary search to repeatedly halve the search space

Algorithm Walkthrough

  1. Initialize two pointers, left and right.

The left pointer starts at index 0, and the right pointer starts at len(nums) - 1. These pointers define the current search range. 2. Continue searching while left <= right.

As long as the search range is valid, there may still be a possible location for the target. 3. Compute the middle index.

We calculate:

$mid = left + \frac{right - left}{2}$

This formula avoids potential integer overflow in some programming languages, although Python itself does not overflow on integers. 4. Compare the middle element with the target.

  • If nums[mid] == target, we immediately return mid because we found the target.
  • If nums[mid] < target, the target must lie to the right of mid, so we move left = mid + 1.
  • If nums[mid] > target, the target must lie to the left of mid, so we move right = mid - 1.
  1. Repeat until the search space becomes empty.

When left > right, the loop stops. At this moment, the left pointer represents the exact insertion position for the target. 6. Return left.

Even if the target does not exist, left indicates the first valid position where the target can be inserted while preserving sorted order.

Why it works

The algorithm maintains an important invariant throughout execution: if the target exists, it must always remain within the current search range. Each comparison removes half of the remaining possibilities while preserving this invariant. When the loop ends, all impossible positions have been eliminated, and the left pointer ends up at the smallest index where the target could legally appear. This guarantees both correctness and optimal logarithmic runtime.

Python Solution

from typing import List

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

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

            if nums[mid] == target:
                return mid

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

        return left

The implementation begins by initializing the binary search boundaries with left and right. These variables track the current range in which the target may exist.

Inside the while loop, the midpoint is calculated using left + (right - left) // 2. This safely computes the middle index and avoids overflow concerns in languages with fixed integer sizes.

The next section performs the key comparison logic. If the middle element equals the target, the function immediately returns the index. Otherwise, the algorithm determines which half of the array can be discarded:

  • If the middle value is smaller than the target, the left half including mid cannot contain the answer, so left moves to mid + 1.
  • If the middle value is larger than the target, the right half including mid cannot contain the answer, so right moves to mid - 1.

Eventually, the search space becomes empty. At that point, left points to the correct insertion location, so the function returns left.

Go Solution

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

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

        if nums[mid] == target {
            return mid
        }

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

    return left
}

The Go implementation follows the exact same binary search logic as the Python solution. One notable detail is that Go uses integer division automatically when dividing integers, so (right-left)/2 already produces an integer midpoint.

Go slices behave similarly to dynamic arrays, so accessing elements with nums[mid] works naturally. Since the problem guarantees at least one element in the array, no special handling for empty slices is necessary.

The midpoint calculation uses left + (right-left)/2, which avoids overflow in languages with fixed integer sizes such as Go.

Worked Examples

Example 1

Input:

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

We search for the value 5.

Iteration left right mid nums[mid] Action
1 0 3 1 3 Target is larger, move left to 2
2 2 3 2 5 Target found, return 2

Final answer:

2

Example 2

Input:

nums = [1,3,5,6]
target = 2
Iteration left right mid nums[mid] Action
1 0 3 1 3 Target is smaller, move right to 0
2 0 0 0 1 Target is larger, move left to 1

The loop stops because left = 1 and right = 0.

The insertion position is:

1

Example 3

Input:

nums = [1,3,5,6]
target = 7
Iteration left right mid nums[mid] Action
1 0 3 1 3 Target is larger, move left to 2
2 2 3 2 5 Target is larger, move left to 3
3 3 3 3 6 Target is larger, move left to 4

The loop stops because left = 4 and right = 3.

The insertion position is:

4

Complexity Analysis

Measure Complexity Explanation
Time O(log n) Each iteration cuts the search space in half
Space O(1) Only a few variables are used regardless of input size

The runtime is logarithmic because binary search eliminates half of the remaining elements during every iteration. Starting with n elements, the search space shrinks to n/2, then n/4, then n/8, and so on until only one possibility remains.

The space complexity is constant because the algorithm uses only a fixed number of variables such as left, right, and mid. No additional data structures proportional to input size are allocated.

Test Cases

from typing import List

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

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

            if nums[mid] == target:
                return mid

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

        return left

solution = Solution()

assert solution.searchInsert([1, 3, 5, 6], 5) == 2  # target exists in middle
assert solution.searchInsert([1, 3, 5, 6], 2) == 1  # insert between elements
assert solution.searchInsert([1, 3, 5, 6], 7) == 4  # insert at end
assert solution.searchInsert([1, 3, 5, 6], 0) == 0  # insert at beginning
assert solution.searchInsert([1], 1) == 0  # single element found
assert solution.searchInsert([1], 0) == 0  # single element insert before
assert solution.searchInsert([1], 2) == 1  # single element insert after
assert solution.searchInsert([1, 2, 4, 6, 8], 5) == 3  # insert in middle gap
assert solution.searchInsert([-10, -3, 0, 5, 9], -3) == 1  # negative number found
assert solution.searchInsert([-10, -3, 0, 5, 9], 4) == 3  # negative and positive mix
Test Why
[1,3,5,6], target=5 Validates finding an existing value
[1,3,5,6], target=2 Validates insertion in the middle
[1,3,5,6], target=7 Validates insertion at the end
[1,3,5,6], target=0 Validates insertion at the beginning
[1], target=1 Tests single element exact match
[1], target=0 Tests insertion before a single element
[1], target=2 Tests insertion after a single element
[1,2,4,6,8], target=5 Tests insertion into an internal gap
[-10,-3,0,5,9], target=-3 Tests negative number matching
[-10,-3,0,5,9], target=4 Tests mixed negative and positive values

Edge Cases

One important edge case occurs when the target is smaller than every element in the array. A buggy implementation may incorrectly return -1 or fail to handle the left boundary properly. In this implementation, the binary search eventually moves right below 0, while left remains 0. Returning left correctly places the target at the beginning of the array.

Another critical edge case is when the target is larger than every element. Some implementations mistakenly return the last valid index instead of the insertion position after the array. In this solution, the left pointer eventually advances to len(nums), which correctly represents insertion at the end.

A third important case involves arrays with only one element. Binary search implementations are especially prone to off by one errors in very small arrays because the loop conditions become sensitive. This implementation handles single element arrays naturally because the search loop still evaluates correctly, and the final return value accurately reflects either a match or the correct insertion location.

A final subtle edge case occurs when the target falls between two existing elements. The algorithm must return the exact insertion position rather than the nearest value. Because the binary search narrows the range until left becomes the first valid insertion index, the implementation guarantees the correct placement between adjacent elements.