Skip to main content
CodePeetCodePeet
CodePeet 250

Search Insert Position

EASYProblemSolveExternal Links

Description

Given a sorted array of distinct integers nums and a target value, return the index if the target is found. If it is not found, return the index where it would be inserted in order so that the array remains sorted.

You must write an algorithm with O(log n) runtime complexity.

Examples

Example 1

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

Output: 2

Explanation: The target value 5 is found at index 2 in the array, so we return 2.

Example 2

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

Output: 1

Explanation: The target value 2 is not in the array. If we inserted 2, it would go between 1 and 3, at index 1. So we return 1.

Example 3

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

Output: 4

Explanation: The target value 7 is greater than every element in the array. It would be inserted at the end, at index 4 (the length of the array). So we return 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

Editorial

Brute Force

Intuition

The most straightforward way to think about this problem is:

Walk through the array from left to right. The moment you find an element that is greater than or equal to the target, you have found the answer — that is the position where the target either already exists or should be inserted.

Why does this work? Because the array is sorted in ascending order. Every element before the first element ≥ target is strictly less than the target, meaning the target belongs after all of them. And the first element ≥ target is exactly the correct boundary.

If we finish scanning the entire array without finding any element ≥ target, then the target is larger than every element, and it should be placed at the very end (index = array length).

Step-by-Step

Let's trace through nums = [1, 3, 5, 6], target = 2 step by step:

Step 1: Start with index i = 0. Check nums[0] = 1. Is 1 ≥ 2? No. Move to the next element.

Step 2: Move to index i = 1. Check nums[1] = 3. Is 3 ≥ 2? Yes! We found the first element that is greater than or equal to target. Return index 1.

The answer is 1 — if we insert 2 at index 1, the array becomes [1, 2, 3, 5, 6], which is still sorted.

Now let's trace nums = [1, 3, 5, 6], target = 7 (target larger than all elements):

Step 1: i = 0, nums[0] = 1, 1 < 7 → continue.

Step 2: i = 1, nums[1] = 3, 3 < 7 → continue.

Step 3: i = 2, nums[2] = 5, 5 < 7 → continue.

Step 4: i = 3, nums[3] = 6, 6 < 7 → continue.

Step 5: We've exhausted the array without finding any element ≥ 7. Return nums.length = 4. The target goes at the end.

Algorithm

  1. Iterate through the array from index 0 to n - 1.
  2. At each index i, check if nums[i] >= target.
  3. If yes, return i — this is the position where the target exists or should be inserted.
  4. If the loop finishes without returning, return n (the array length) — the target is larger than all elements and belongs at the end.

Code

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] >= target) {
                return i;
            }
        }
        return nums.size();
    }
};
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)
class Solution {
    public int searchInsert(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] >= target) {
                return i;
            }
        }
        return nums.length;
    }
}

Complexity Analysis

Time Complexity: O(n)

In the worst case (target is larger than all elements, or target equals the last element), we scan every element in the array exactly once.

Space Complexity: O(1)

We only use a single loop variable i. No additional data structures are allocated.

Why This Approach Is Not Efficient

The brute force approach scans elements one by one from left to right. In the worst case, it checks every single element, resulting in O(n) time complexity.

But think about it — we are completely ignoring the fact that the array is sorted. When an array is sorted, we have powerful information:

If the middle element is less than the target, then all elements to the left of it are also less than the target. We can discard the entire left half in one step.

This is the fundamental insight behind Binary Search. Instead of eliminating one element per step (linear scan), binary search eliminates half the remaining elements per step. This reduces the time from O(n) to O(log n).

For an array of 10,000 elements:

  • Linear scan: up to 10,000 comparisons
  • Binary search: at most ~14 comparisons (log₂(10000) ≈ 13.3)

The problem statement even explicitly requires O(log n) runtime, making binary search the expected approach.

Optimal Approach

Intuition

Since the array is sorted, we can use Binary Search to find the target or its insertion position in O(log n) time.

The key insight is:

At the end of a binary search, if the target is not found, the left pointer naturally points to the correct insertion position.

Why? Let's think about what happens during binary search:

  • We maintain two pointers: left and right, representing the current search window.
  • At each step, we compute mid = left + (right - left) / 2 and compare nums[mid] with target.
  • If nums[mid] == target, we return mid immediately.
  • If nums[mid] < target, the target must be to the right, so we set left = mid + 1.
  • If nums[mid] > target, the target must be to the left, so we set right = mid - 1.

When the loop ends (left > right), the left pointer is positioned at the smallest index where nums[left] would be ≥ target. This is exactly the insertion position!

This works because every time we set left = mid + 1, we are saying "the target belongs after index mid". And every time we set right = mid - 1, we are saying "the target belongs at or before index mid". When the pointers cross, left captures the exact boundary.

Step-by-Step

Let's trace through nums = [1, 3, 5, 6], target = 2 using binary search:

Step 1: Initialize left = 0, right = 3. Search window is the entire array [1, 3, 5, 6].

Step 2: Compute mid = 0 + (3 - 0) / 2 = 1. Check nums[1] = 3. Is 3 == 2? No. Is 3 > 2? Yes. So target is in the left half. Set right = mid - 1 = 0.

Step 3: Now left = 0, right = 0. Compute mid = 0. Check nums[0] = 1. Is 1 == 2? No. Is 1 < 2? Yes. So target is in the right half. Set left = mid + 1 = 1.

Step 4: Now left = 1, right = 0. Since left > right, the loop ends. Return left = 1.

The answer is 1 — the same result as brute force, but we only made 2 comparisons instead of potentially scanning all elements.

Now let's trace nums = [1, 3, 5, 6], target = 5 (target is present in the array):

Step 1: left = 0, right = 3. Compute mid = 1. nums[1] = 3 < 5 → set left = 2.

Step 2: left = 2, right = 3. Compute mid = 2. nums[2] = 5 == 5 → found! Return 2.

Binary search found the exact target in just 2 comparisons.

Algorithm

  1. Initialize left = 0 and right = nums.length - 1.
  2. While left <= right:
    • Compute mid = left + (right - left) / 2 (avoids integer overflow).
    • If nums[mid] == target, return mid — target found.
    • If nums[mid] < target, set left = mid + 1 — target is in the right half.
    • If nums[mid] > target, set right = mid - 1 — target is in the left half.
  3. If the loop ends without finding the target, return left — this is the correct insertion position.

Code

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;
        
        while (left <= right) {
            int 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;
    }
};
class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1
        
        while left <= right:
            mid = left + (right - left) // 2
            
            if nums[mid] == target:
                return mid
            elif nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
        
        return left
class Solution {
    public int searchInsert(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        
        while (left <= right) {
            int 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;
    }
}

Complexity Analysis

Time Complexity: O(log n)

At each iteration, binary search halves the search window. Starting with n elements, after k iterations we have n / 2^k elements remaining. The loop terminates when n / 2^k < 1, which gives k = log₂(n). So we make at most O(log n) comparisons.

Space Complexity: O(1)

We only use three integer variables (left, right, mid). No additional data structures are allocated, and the algorithm is iterative (no recursion stack).