Skip to main content

Binary Search

Search Insert Position Solution In C++/Java/Python/JS

Problem Description:

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.
Illustration explaining the Problem Description of Search Insert Position

Examples:

Input: nums = [1,3,5,6], target = 5
Output: 2
Explanation: target=5 must be inserted at index = 2 to maintain the sorted order.

Input: nums = [1,3,5,6], target = 2
Output: 1
Explanation: target=2 must be inserted at index = 1 to maintain the sorted order.

Input: nums = [1,3,5,6], target = 7
Output: 4
Explanation: target=7 must be inserted at index = 4 to maintain the sorted order.

Constraints:

  • 1 <= nums.length <= 104
  • -104 <= nums[i] <= 104
  • nums contains distinct values sorted in ascending order.
  • -104 <= target <= 104

Brute Force Approach

Intuition:

To solve the Search Insert Position problem, let's carefully analyze the requirements. We are given a sorted array of distinct integers, nums and a target value. The task is to find the index where the target should be inserted in the array so that it remains sorted.

A straightforward way to approach this problem is to directly simulate the process of inserting the target into a sorted array. The key idea is simple:

  • All elements before the target should be less than the target.
  • All elements after the target should be greater than or equal to the target.

This means the correct insertion point is the first index where the element is greater than or equal to the target. If no such element is found, that means the target is greater than all elements and should be inserted at the end.

To implement this, we can loop through the array step-by-step:

Start checking each element from the beginning of the array. If the current element nums[i] is greater than or equal to the target, return i because that’s the correct position to keep the array sorted.

If we reach the end of the array without finding such an element, that means the target is greater than all existing elements, so it should be inserted at the end.

Example:

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

  • Start from the first element:
    • 1 < 2 → Keep going
    • 3 >= 2 → Insert 2 at index 1
  • The correct output is 1 because inserting 2 at index 1 keeps the array sorted as [1, 2, 3, 5, 6].
Illustration explaining the Brute Force Approach

Search Insert Position Example

input: nums = [3, 5, 6, 11, 14], target = 4
Output: 1
Explanation: 4 must be inserted between 3 and 5 at index 1 for the array nums to remain sorted.

Initial Setup:

  • n = nums.size() → n = 5
  • i is initialized but not yet assigned a value

Step-by-Step Dry Run:

Iteration 1:

  • i = 0
  • nums[0] = 3
  • Condition: nums[0] >= target → 3 >= 4 → False
  • Continue to next iteration

Iteration 2:

  • i = 1
  • nums[1] = 5
  • Condition: nums[1] >= target → 5 >= 4 → True
  • Return i = 1

Final Answer:

Since nums[1] = 5 is the first element greater than or equal to the target, the target should be inserted at index 1 to keep the array sorted.

Search Insert Position Algorithm

Step 1: Initialize Variables

  • Define the following variables:
  • n → size of the input array (nums).
  • i → loop variable to scan through the array.

Step 2: Loop Through the Array

  • Use a for loop to check each element in the array one by one.
  • Start the loop from i = 0 and go up to n - 1.

Step 3: Check If the Current Element is Greater or Equal to Target

  • Inside the loop, check if nums[i] >= target:
    • If true → return i because this is the correct insertion position (or the element already exists).

Step 4: If No Element is Greater or Equal to Target

  • If the loop finishes and no element is greater than or equal to the target:
    • The target should be inserted at the end of the array.
    • Return i (which will be equal to n at this point).
Search Insert Position solutions
Search Insert Position solution in C++ 
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        // Get the size of the array
        int n = nums.size(); 

        int i;
        // Loop through the array
        for (i = 0; i < n; ++i) { 
            // If the current element is greater or equal to target
            if (nums[i] >= target) { 
                return i; // Return the index
            }
        }

        // If no element is greater, return the index at the end
        return i; 
    }
};

Search Insert Position solution in Java 
class Solution {
    public int searchInsert(int[] nums, int target) {
        // Get the size of the array
        int n = nums.length;

        int i;
        // Loop through the array
        for (i = 0; i < n; ++i) {
            // If the current element is greater or equal to target
            if (nums[i] >= target) {
                return i; // Return the index
            }
        }

        // If no element is greater, return the index at the end
        return i;
    }
}

Search Insert Position solution in Python 
class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        # Get the size of the array
        n = len(nums)

        # Loop through the array
        for i in range(n):
            # If the current element is greater or equal to target
            if nums[i] >= target:
                return i  # Return the index
        
        # If no element is greater, return the index at the end
        return n

Search Insert Position solution in Javascript 
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var searchInsert = function(nums, target) {
        // Get the size of the array
        let n = nums.length;

        // Loop through the array
        for (let i = 0; i < n; ++i) {
            // If the current element is greater or equal to target
            if (nums[i] >= target) {
                return i; // Return the index
            }
        }

        // If no element is greater, return the index at the end
        return n;
    }
}

Search Insert Position Complexity Analysis

Time Complexity:  O(n)

To analyze the time complexity, let's carefully examine the structure of the code:

Loop Complexity

  • The for loop runs from i = 0 to i = n - 1, where n is the size of the array (nums).
  • In the worst case, the loop will need to check every element in the array until the end.
  • This gives a maximum of n iterations in the worst case.
  • Hence time complexity is O(n)

Final Time Complexity: O(n)

Space Complexity: O(1)

To analyze the space complexity, let's break it down step-by-step:

1. Auxiliary Space Complexity

Auxiliary space refers to the extra space used by the algorithm beyond the input data.

  • We are using a few integer variables
    • n → to store the size of the array → O(1)
    • i → to control the loop → O(1)
  • No additional data structures like arrays or stacks are used.

Auxiliary Space Complexity: O(1)

2. Total Space Complexity

Total space complexity includes both the input size and any extra space used during execution.

  • Input array nums of size n is already provided as input, so it counts toward total space: O(n)
  • Auxiliary space is O(1) as analyzed earlier.

Total Overall Space Complexity: O(n)+O(1)=O(n)

Is the brute force approach efficient ?

For n ≤ 10 ⁴, our solution has a time complexity of O(N), which will comfortably meet the given constraints.

This is well within the time limits of most competitive programming environments, which typically allow around 1-2 seconds for execution.

In such environments, it is common for problems to handle up to 10⁶ operations within these limits.

Most competitive programming platforms, like Leet Code, allow up to 10⁶ operations per test case, meaning your solution should be able to handle this number of operations within the time limits. When multiple test cases are involved, the total number of operations can go up to 10⁸.

Optimal Approach

Intuition:

To solve the Search Insert Position problem more efficiently, let’s take a step back and think about the brute-force solution.

The brute force solution involves a for loop to find the correct insertion position, which gives us a time complexity of O(n). This works fine for small inputs but becomes inefficient for larger arrays.

How Can We Improve It?

The main bottleneck is the for loop — it forces us to check each element one by one. To improve the solution, we need to remove this linear scanning and find a faster way to locate the insertion point.

Let’s think about the problem more carefully:

  • The array is already sorted.
  • We are tasked with finding the first element greater than or equal to the target.
  • A sorted array naturally hints at a more efficient search mechanism — something faster than a linear scan.

Why Sorting Helps

In a sorted array:

  • All elements to the left of any given index are smaller than or equal to the element at that index.
  • All elements to the right of any given index are greater than or equal to the element at that index.

This property allows us to skip large portions of the array when searching, because we know the elements are already arranged in order.

For example, if the array is [1, 3, 5, 6] and the target is 2, once we encounter 3, we know that there’s no need to check any elements after 3 because they will all be larger than 2.

Instead of checking each element one by one, let's try something different — let’s directly pick the middle element of the array and see how it compares to the target.

Suppose we have: nums = [1, 3, 5, 6], target = 2

We take the middle element:

  • The middle index is mid = 1 → nums[mid] = 3

Now we have two possible cases to consider:

Case 1: If nums[mid] is greater than or equal to the target

In this case, the target should be inserted to the left of mid or at mid itself.

Why?

  • Since the array is sorted, any element to the right of the mid will be larger than nums[mid].
  • So if nums[mid] is already greater than or equal to the target, placing the target to the right side would make the array unsorted.
  • Therefore, the target should be inserted at mid or somewhere to its left.

In the example:

  • nums[mid] = 3, which is greater than 2.
  • So, the target should be on the left side of mid or at mid

Therefore, we need to search in the left half of the array also marking our answer to mid.

Illustration showing the Case1 of the Optimal Approach.

Case 2: If nums[mid] is less than the target

If nums[mid] is less than the target, that means the target should be inserted to the right of mid.

Why?

  • Since the array is sorted, all elements to the left of the mid are smaller than nums[mid].
  • If nums[mid] is already smaller than the target, the correct insertion point has to be on the right side.

In the example:

  • If target = 5, nums[mid] = 3 would be smaller.
  • So, we discard the left side and search in the right half.
Illustration showing the Case 2 of the Optimal Approach.

Notice how the search space is reduced to half after every step. Instead of checking each element one by one, we are systematically narrowing down the search area by discarding half of the array at each step.

This is exactly how a binary search works — but instead of searching for an element, we are searching for the correct insertion position.

💡
Binary Search in detail !
0:00
/1:12

Animation showing How Optimal Approach Works

Search Insert Position Example

input: nums = [3, 5, 6, 11, 14], target = 4
Output: 1
Explanation: 4 must be inserted between 3 and 5 at index 1 for the array nums to remain sorted.

Initial Setup:

  • n = nums.size() → n = 5
  • low = 0
  • high = n - 1 = 4
  • index = n = 5

Step-by-Step Dry Run:

First Iteration:

  • low = 0, high = 4
  • Calculate mid: mid=(0+4)/2=2
  • nums[mid] = nums[2] = 6
  • Condition: nums[mid] >= target → 6 >= 4 → True
    • Update index = mid = 2
    • Update high = mid - 1 = 2 - 1 = 1

Second Iteration:

  • low = 0, high = 1
  • Calculate mid: mid= (0+1) / 2=0
  • nums[mid] = nums[0] = 3
  • Condition: nums[mid] >= target → 3 >= 4 → False
    • Update low = mid + 1 = 0 + 1 = 1

Third Iteration:

  • low = 1, high = 1
  • Calculate mid: mid=(1+1) / 2 = 1
  • nums[mid] = nums[1] = 5
  • Condition: nums[mid] >= target → 5 >= 4 → True
    • Update index = mid = 1
    • Update high = mid - 1 = 1 - 1 = 0

Termination:

  • low = 1, high = 0 → low > high
  • Exit the loop

Final Answer:

Since index = 1, the target should be inserted at index 1 to keep the array sorted.

Search Insert Position Algorithm

Let's go step-by-step through the process of writing this code:

Step 1: Initialize Variables

  • First, determine the size of the array nums.
  • We need two pointers to define the search range:
    • low → starting index of the array (0)
    • high → last index of the array (n - 1)
  • Create a variable index to store the potential insertion position.
    • Initially set it to n (position after the last element).

Step 2: Start Binary Search Loop

  • Use a while loop to perform binary search.
  • Condition: Run the loop as long as low <= high (ensuring the search range is valid).

Step 3. Find the Middle Element

  • Calculate the middle index of the current search range.
  • Get the mid index.

Step 4. Handle Different Cases

  • Case 1: If nums[mid] >= target
    • This means the target can potentially be inserted at mid.
    • So, update index = mid.
    • Since we want the leftmost position, continue searching the left half by setting high = mid - 1.
  • Case 2: If nums[mid] < target
    • This means the target should be placed after mid.
    • Search the right half by setting low = mid + 1.

Step 5. Return the Result

  • After the loop ends, index will hold the correct insertion position.
  • Return index as the final result.

Search Insert Position Leetcode solutions
Search Insert Position solution in C++ 
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
		// Step 1: Get the size of the array
        int n = nums.size(); 
        
        int low = 0, high = n - 1;
		// Step 2: Initialize index to n (end of the array)
        int index = n; 

        // Step 3: Perform binary search
        while (low <= high) {
			// Step 3a: Find the middle index
            int mid = (low + high) / 2; 
            
            if (nums[mid] >= target) {
                // Step 3b: If nums[mid] is greater or equal to target, mark index and search left side
                index = mid;
                high = mid - 1;
            } else {
                // Step 3c: If nums[mid] is smaller than target, search right side
                low = mid + 1;
            }
        }
		// Step 4: Return the final insertion index
        return index; 
    }
};

Search Insert Position Leetcode solution in Java 
class Solution {
    public int searchInsert(int[] nums, int target) {
		// Step 1: Get the size of the array
        int n = nums.length; 
        
        int low = 0, high = n - 1;
		// Step 2: Initialize index to n (end of the array)
        int index = n; 

        // Step 3: Perform binary search
        while (low <= high) {
			// Step 3a: Find the middle index
            int mid = (low + high) / 2; 
            
            if (nums[mid] >= target) {
                // Step 3b: If nums[mid] is greater or equal to target, mark index and search left side
                index = mid;
                high = mid - 1;
            } else {
                // Step 3c: If nums[mid] is smaller than target, search right side
                low = mid + 1;
            }
        }
		// Step 4: Return the final insertion index
        return index; 
    }
}

Search Insert Position Leetcode solution in Python 
class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        n = len(nums) # Step 1: Get the size of the array
        
        low, high = 0, n - 1
        # Step 2: Initialize index to n (end of the array)
        index = n 

        # Step 3: Perform binary search
        while low <= high:
            # Step 3a: Find the middle index
            mid = (low + high) // 2 
            
            if nums[mid] >= target:
                # Step 3b: If nums[mid] is greater or equal to target, mark index and search left side
                index = mid
                high = mid - 1
            else:
                # Step 3c: If nums[mid] is smaller than target, search right side
                low = mid + 1
        
        # Step 4: Return the final insertion index
        return index

Search Insert Position Leetcode solution in Javascript 
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var searchInsert = function(nums, target) {
    
        // Step 1: Get the size of the array
        let n = nums.length; 
        
        let low = 0, high = n - 1;
        // Step 2: Initialize index to n (end of the array)
        let index = n; 

        // Step 3: Perform binary search
        while (low <= high) {
            // Step 3a: Find the middle index
            let mid = Math.floor((low + high) / 2); 
            
            if (nums[mid] >= target) {
                // Step 3b: If nums[mid] is greater or equal to target, mark index and search left side
                index = mid;
                high = mid - 1;
            } else {
                // Step 3c: If nums[mid] is smaller than target, search right side
                low = mid + 1;
            }
        }

        // Step 4: Return the final insertion index
        return index; 
    }
}

Search Insert Position Complexity Analysis

Time Complexity: O(logn)

Let’s carefully analyze the time complexity of the given code step-by-step:

1. Initialization Step

  • We are initializing a few variables at the start:
    • n = nums.size() → Takes O(1)
    • low = 0, high = n - 1, index = n
    • Initialization Step Complexity: O(1)

2. Binary Search Step

The main work is done inside the while loop, which executes a binary search.

Binary Search Explanation:

  • The binary search works by reducing the search space by half at each step.
  • Let's see how it happens:
    • Start with a search range of size n.
    • After the first comparison, the search space becomes n/2.
    • After the second comparison, the search space becomes n/4.
    • After the third comparison, the search space becomes n/8.
    • This continues until the search space reduces to 1.

General Pattern:

  • At each step, the search space is divided by 2.
  • Therefore, the number of steps required to reduce the search space to size 1 is approximately: log⁡2 n
  • Thus, the number of iterations in the while loop is log2 n.

Work Done Per Iteration:

  • Inside the loop, the following operations happen:
    • Computing mid = (low + high) / 2 → O(1)
    • Comparison and updating index, low, and high → O(1) Total Work Per Iteration: O(1)

Number of Iterations: O(log⁡n)

Therefore, the total work done inside the loop is: O(1)×O(log⁡n)=O(log⁡n)

3. Return Step

  • Returning the result takes constant time → O(1)

Final Time Complexity

Adding all parts together:

  • Initialization → O(1)
  • Binary Search → O(log n)
  • Return → O(1)

Final Answer: O(1)+O(log⁡n)+O(1)=O(log⁡n)

Space Complexity: O(1)

Let’s carefully analyze the space usage in the code step-by-step:

1. Auxiliary Space Complexity

Auxiliary space refers to the extra space used by the algorithm excluding the input array.

In the given code, we are using the following extra variables:

  • n → To store the size of the array → O(1)
  • low → To track the starting index of the search range → O(1)
  • high → To track the ending index of the search range → O(1)
  • index → To store the result → O(1)
  • mid → To calculate the middle index → O(1)

All of these are simple integer variables that take constant space.

Auxiliary Space Complexity: O(1)

2. Total Space Complexity

Total space complexity is the sum of Auxiliary space and Input space

Input Space Complexity

  • The input array nums is passed as a reference, so no additional space is allocated for it within the function.
  • Therefore, input space does not contribute to the auxiliary space.
  • Auxiliary space = O(1)
  • Input space = O(n) (since nums has n elements)

Final Answer: O(1)+O(n)=O(n)

Similar Problems

Now we have successfully tackled this problem, let's try these similar problems:-

1. First Bad Version

You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.

Suppose you have n versions [1, 2, ..., n] and you want to find out the first bad one, which causes all the following ones to be bad.

You are given an API bool isBadVersion(version) which returns whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

2. Minimum Operations to Exceed Threshold Value I

You are given a 0-indexed integer array nums, and an integer k.

In one operation, you can remove one occurrence of the smallest element of nums.

Return the minimum number of operations needed so that all elements of the array are greater than or equal to k.