Search Insert Position

Problem Statement

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.

What to notice first

• The array is sorted, which suggests a binary search solution.
• If the target is not found, the search pointers converge to the insertion position.
• The left pointer at the end of binary search always points to where the target should be inserted.

Examples

Input	Target	Output	Explanation
[1, 3, 5, 6]	5	2	Target found at index 2
[1, 3, 5, 6]	2	1	Insert at index 1 to maintain sort order
[1, 3, 5, 6]	7	4	Insert at end (index 4)

Constraints

• 1 <= nums.length <= 10^4
• -10^9 <= nums[i] <= 10^9
• All elements are distinct
• -10^9 <= target <= 10^9

Real-World Applications

Where this pattern appears

• Database indexing — finding the correct position to insert a new record while maintaining sort order.
• Sorted list maintenance — keeping a dynamic sorted structure as new elements arrive.
• Library shelf placement — determining where a book should go in a sorted catalog.
• Event scheduling — inserting a new event at the correct time slot in a timeline.

Complexity Comparison

Approach	Time	Space	Best When
Binary Search	O(log n)	O(1)	Standard approach — sorted array, optimal runtime
Linear Search	O(n)	O(1)	Small arrays, simplicity preferred over speed

Which approach should you learn first?

• Pick Binary Search if you want the optimal O(log n) solution and understand the pattern.
• Pick Linear Search if you are still learning or the array is small.

Best For Speed

Binary Search

O(log n) time · O(1) space

Simplicity

Linear Search

O(n) time · O(1) space

Approach 1: Binary Search (Recommended)

★ Recommended

Use binary search on the sorted array. The key insight is that when the target is not found, the left pointer converges to the insertion position.

⏱ Time O(log n) Halve search space each iteration 💾 Space O(1) Only pointers

Step-by-step Example

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

Step	left	right	mid	nums[mid]	Action
1	0	3	1	3	3 > 2 → right = 0
2	0	0	0	1	1 < 2 → left = 1
3	1	0	—	—	left > right, exit. left = 1 is insertion point ✓

Pseudocode

function searchInsert(nums, target):
    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  // Insertion point

Solution Code

Python

search_insert_position_binary_search.py

"""
#35 Search Insert Position - Binary Search Approach
Time: O(log n), Space: O(1)

Given a sorted array and a target value, return the index if found,
otherwise return the index where it would be if it were inserted.
"""


class Solution:
    def searchInsert(self, nums: list[int], target: int) -> int:
        """
        Binary search to find insert position.
        Left pointer converges to insertion point.
        """
        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

        # left is at insertion position when target not found
        return left


# Test cases
if __name__ == "__main__":
    sol = Solution()

    assert sol.searchInsert([1, 3, 5, 6], 5) == 2
    assert sol.searchInsert([1, 3, 5, 6], 2) == 1
    assert sol.searchInsert([1, 3, 5, 6], 7) == 4
    assert sol.searchInsert([1, 3, 5, 6], 0) == 0
    assert sol.searchInsert([], 1) == 0

    print("All test cases passed!")

C++

search_insert_position_binary_search.cpp

#include <vector>
using namespace std;

/*
#35 Search Insert Position - Binary Search Approach
Time: O(log n), Space: O(1)

Given a sorted array and a target value, return the index if found,
otherwise return the index where it would be if it were inserted.
*/

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        /*
        Binary search to find insert position.
        Left pointer converges to insertion point.
        */
        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;
            }
        }

        // left is at insertion position when target not found
        return left;
    }
};

Java

SearchInsertPositionBinarySearch.java

/*
#35 Search Insert Position - Binary Search Approach
Time: O(log n), Space: O(1)

Given a sorted array and a target value, return the index if found,
otherwise return the index where it would be if it were inserted.
*/

class Solution {
    public int searchInsert(int[] nums, int target) {
        /*
        Binary search to find insert position.
        Left pointer converges to insertion point.
        */
        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;
            }
        }

        // left is at insertion position when target not found
        return left;
    }
}

JavaScript

search_insert_position_binary_search.js

/**
 * #35 Search Insert Position - Binary Search Approach
 * Time: O(log n), Space: O(1)
 *
 * Given a sorted array and a target value, return the index if found,
 * otherwise return the index where it would be if it were inserted.
 */

class Solution {
    searchInsert(nums, target) {
        /**
         * Binary search to find insert position.
         * Left pointer converges to insertion point.
         */
        let left = 0, right = nums.length - 1;

        while (left <= right) {
            const mid = left + Math.floor((right - left) / 2);

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

        // left is at insertion position when target not found
        return left;
    }
}

// Export for CommonJS
module.exports = Solution;

Rust

search_insert_position_binary_search.rs

/*
#35 Search Insert Position - Binary Search Approach
Time: O(log n), Space: O(1)

Given a sorted array and a target value, return the index if found,
otherwise return the index where it would be if it were inserted.
*/

impl Solution {
    pub fn search_insert(nums: Vec<i32>, target: i32) -> i32 {
        /*
        Binary search to find insert position.
        Left pointer converges to insertion point.
        */
        let mut left = 0i32;
        let mut right = nums.len() as i32 - 1;

        while left <= right {
            let mid = left + (right - left) / 2;
            let mid_val = nums[mid as usize];

            if mid_val == target {
                return mid;
            } else if mid_val < target {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        // left is at insertion position when target not found
        left
    }
}

Go

search_insert_position_binary_search.go

package main

/*
#35 Search Insert Position - Binary Search Approach
Time: O(log n), Space: O(1)

Given a sorted array and a target value, return the index if found,
otherwise return the index where it would be if it were inserted.
*/

func SearchInsertBinarySearch(nums []int, target int) int {
  /*
  Binary search to find insert position.
  Left pointer converges to insertion point.
  */
  left, right := 0, len(nums)-1

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

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

  // left is at insertion position when target not found
  return left
}

Approach 2: Linear Search

✓ Simple

Scan through the array and return the index of the first element that is greater than or equal to the target.

⏱ Time O(n) Full array scan 💾 Space O(1) Only pointers

Step-by-step Example

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

i	nums[i]	nums[i] >= target?	Action
0	1	No	Continue
1	3	Yes	Return 1 ✓

Pseudocode

function searchInsert(nums, target):
    for i in range(len(nums)):
        if nums[i] >= target:
            return i
    return len(nums)

Solution Code

Python

search_insert_position_linear_search.py

"""
#35 Search Insert Position - Linear Search Approach
Time: O(n), Space: O(1)

Iterate through array to find position or insertion point.
"""


class Solution:
    def searchInsert(self, nums: list[int], target: int) -> int:
        """
        Linear search through array.
        Return index when found or where it should be inserted.
        """
        for i in range(len(nums)):
            if nums[i] >= target:
                return i

        # If target larger than all elements
        return len(nums)


# Test cases
if __name__ == "__main__":
    sol = Solution()

    assert sol.searchInsert([1, 3, 5, 6], 5) == 2
    assert sol.searchInsert([1, 3, 5, 6], 2) == 1
    assert sol.searchInsert([1, 3, 5, 6], 7) == 4
    assert sol.searchInsert([1, 3, 5, 6], 0) == 0
    assert sol.searchInsert([], 1) == 0

    print("All test cases passed!")

C++

search_insert_position_linear_search.cpp

#include <vector>
using namespace std;

/*
#35 Search Insert Position - Linear Search Approach
Time: O(n), Space: O(1)

Iterate through array to find position or insertion point.
*/

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        /*
        Linear search through array.
        Return index when found or where it should be inserted.
        */
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] >= target) {
                return i;
            }
        }

        // If target larger than all elements
        return nums.size();
    }
};

Java

SearchInsertPositionLinearSearch.java

/*
#35 Search Insert Position - Linear Search Approach
Time: O(n), Space: O(1)

Iterate through array to find position or insertion point.
*/

class Solution {
    public int searchInsert(int[] nums, int target) {
        /*
        Linear search through array.
        Return index when found or where it should be inserted.
        */
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] >= target) {
                return i;
            }
        }

        // If target larger than all elements
        return nums.length;
    }
}

JavaScript

search_insert_position_linear_search.js

/**
 * #35 Search Insert Position - Linear Search Approach
 * Time: O(n), Space: O(1)
 *
 * Iterate through array to find position or insertion point.
 */

class Solution {
    searchInsert(nums, target) {
        /**
         * Linear search through array.
         * Return index when found or where it should be inserted.
         */
        for (let i = 0; i < nums.length; i++) {
            if (nums[i] >= target) {
                return i;
            }
        }

        // If target larger than all elements
        return nums.length;
    }
}

// Export for CommonJS
module.exports = Solution;

Rust

search_insert_position_linear_search.rs

/*
#35 Search Insert Position - Linear Search Approach
Time: O(n), Space: O(1)

Iterate through array to find position or insertion point.
*/

impl Solution {
    pub fn search_insert(nums: Vec<i32>, target: i32) -> i32 {
        /*
        Linear search through array.
        Return index when found or where it should be inserted.
        */
        for (i, &num) in nums.iter().enumerate() {
            if num >= target {
                return i as i32;
            }
        }

        // If target larger than all elements
        nums.len() as i32
    }
}

Go

search_insert_position_linear_search.go

package main

/*
#35 Search Insert Position - Linear Search Approach
Time: O(n), Space: O(1)

Iterate through array to find position or insertion point.
*/

func SearchInsertLinearSearch(nums []int, target int) int {
  /*
  Linear search through array.
  Return index when found or where it should be inserted.
  */
  for i := 0; i < len(nums); i++ {
    if nums[i] >= target {
      return i
    }
  }

  // If target larger than all elements
  return len(nums)
}

Common mistakes

Watch for these pitfalls

• Forgetting that the left pointer marks the insertion position when target is not found.
• Using mid directly without the offset calculation, causing integer overflow in some languages.
• Returning the wrong value when the target should be inserted at the end of the array.

Approach 3: Space-Optimized Variant

✓ Simple

A third approach demonstrating an alternative technique for solving this problem. This implementation optimizes either time or space complexity compared to the previous approaches.

⏱ Time O(n) Optimized complexity 💾 Space O(1) Efficient space usage

Pseudocode

function approach3():
    // Implementation approach goes here

Solution Code

Python

search_insert_position_space_optimized.py

"""
Solution for Search Insert Position
"""

def solve():
    """Implementation for approach 3 of Search Insert Position"""
    pass

if __name__ == "__main__":
    print("Solution ready")

C++

search_insert_position_space_optimized.cpp

#include <bits/stdc++.h>
using namespace std;

// Solution for Search Insert Position
// Approach 3: Implementation

int main() {{
    // Main implementation goes here
    return 0;
}}

Java

SearchInsertPositionSpaceOptimized.java

/**
 * Solution for Search Insert Position
 * Approach 3
 */
public class SearchInsertPositionSpaceOptimized {{

    public static void main(String[] args) {{
        // Implementation goes here
    }}
}}

JavaScript

search_insert_position_space_optimized.js

/**
 * Solution for Search Insert Position
 * Approach 3
 */

function solve() {{
    // Implementation goes here
}}

module.exports = solve;

Rust

search_insert_position_space_optimized.rs

/// Solution for Search Insert Position
/// Approach 3

fn main() {{
    println!("Solution implementation");
}}

Go

search_insert_position_space_optimized.go

package main

import "fmt"

// Solution for Search Insert Position
// Approach 3

func main() {{
    fmt.Println("Solution implementation")
}}

Related Problems

• Binary Search ↗ Easy #704
• Search in Rotated Sorted Array ↗ Medium #33
• Find First and Last Position of Element in Sorted Array ↗ Medium #34
• Find Peak Element ↗ Medium #162

Interview Tips

Key trade-offs to discuss

• Why binary search? It achieves O(log n) on a sorted array, much faster than linear O(n).
• The insertion point insight: When not found, left naturally points to where the element should be inserted. This is a powerful pattern.
• Edge cases: Empty array, target smaller than all elements, target larger than all elements, array with one element.
• Why linear search might be preferred: If the array is tiny (< 10 elements), linear might be clearer and faster in practice.

← Previous
#34 Find First and Last Position of Element in Sorted Array Next
#36 Valid Sudoku →