35. Search Insert Position - Explanation

Description

You are 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,0,2,4,6,8], target = 5

Output: 4

Example 2:

Input: nums = [-1,0,2,4,6,8], target = 10

Output: 6

Constraints:

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

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Linear Search

Intuition

We scan the array from left to right looking for the first element that is greater than or equal to the target. If we find such an element, that index is where the target either exists or should be inserted. If no element qualifies, the target belongs at the end.

Algorithm

Iterate through each index i in the array.
If nums[i] >= target, return i.
If the loop completes without returning, return n (the length of the array to insert at the end).

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)

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$ extra space.

2. Binary Search - I

Intuition

Since the array is sorted, we can use binary search to find the target in logarithmic time. We track the potential insertion point as we search. Whenever we find an element greater than the target, we update our answer and continue searching left for a potentially smaller valid index.

Algorithm

Initialize res = n (default insertion point at the end) and pointers l = 0, r = n - 1.
While l <= r:
- Compute mid = (l + r) / 2.
- If nums[mid] == target, return mid.
- If nums[mid] > target, set res = mid and search left with r = mid - 1.
- Otherwise, search right with l = mid + 1.
Return res (final insertion position).

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        res = len(nums)
        l, r = 0, len(nums) - 1
        while l <= r:
            mid = (l + r) // 2
            if nums[mid] == target:
                return mid
            if nums[mid] > target:
                res = mid
                r = mid - 1
            else:
                l = mid + 1
        return res

Time & Space Complexity

Time complexity: $O(\log n)$
Space complexity: $O(1)$ extra space.

3. Binary Search - II

Intuition

A cleaner observation: when binary search ends without finding the target, the left pointer l naturally lands on the correct insertion position. This happens because l always moves past elements smaller than the target, stopping exactly where the target should go.

Algorithm

Initialize pointers l = 0 and r = n - 1.
While l <= r:
- Compute mid = (l + r) / 2.
- If nums[mid] == target, return mid.
- If nums[mid] > target, search left with r = mid - 1.
- Otherwise, search right with l = mid + 1.
Return l as the insertion index (where l naturally lands on the correct position).

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

Time & Space Complexity

Time complexity: $O(\log n)$
Space complexity: $O(1)$ extra space.

4. Binary Search (Lower Bound)

Intuition

This is the classic lower bound algorithm. We find the smallest index where the element is greater than or equal to the target. By using l < r as the condition and setting r = m when nums[m] >= target, we converge on the lower bound without needing a separate result variable.

Algorithm

Initialize pointers l = 0 and r = n (note: r starts at n, not n - 1).
While l < r:
- Compute m = l + (r - l) / 2.
- If nums[m] >= target, set r = m.
- Otherwise, set l = m + 1.
Return l (the lower bound position).

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        l, r = 0, len(nums)
        while l < r:
            m = l + ((r - l) // 2)
            if nums[m] >= target:
                r = m
            elif nums[m] < target:
                l = m + 1
        return l

Time & Space Complexity

Time complexity: $O(\log n)$
Space complexity: $O(1)$

5. Built-In Binary Search Function

Intuition

Most languages provide a built-in binary search or lower bound function. These functions return the index where the target is found or the position where it should be inserted to maintain sorted order. Using these avoids reimplementing binary search.

Algorithm

Call the language's built-in binary search function (e.g., bisect_left in Python, lower_bound in C++, Arrays.binarySearch in Java).
If the function returns a negative value (Java), convert it to the insertion point (-index - 1).
Return the resulting index.

import bisect
class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        return bisect.bisect_left(nums, target)

Time & Space Complexity

Time complexity: $O(\log n)$
Space complexity: $O(1)$

Common Pitfalls

Off-by-One Errors in Binary Search Boundaries

A frequent mistake is using incorrect loop conditions or boundary updates. Using l < r instead of l <= r (or vice versa) without adjusting the logic accordingly can cause the algorithm to miss elements or enter infinite loops. Similarly, setting r = mid instead of r = mid - 1 in certain variants can lead to incorrect results or infinite loops.

Forgetting to Handle the "Insert at End" Case

When the target is larger than all elements in the array, the insertion position should be n (the length of the array). Beginners often forget to account for this case, either returning -1, causing an index out of bounds error, or returning the last index incorrectly. Always ensure your algorithm correctly returns n when the target exceeds all array elements.