Search Insert Position - Solution & Explanation
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.
Example 1:
Input: nums = [1,3,5,6], target = 5 Output: 2
Example 2:
Input: nums = [1,3,5,6], target = 2 Output: 1
Example 3:
Input: nums = [1,3,5,6], target = 7 Output: 4
Constraints:
1 <= nums.length <= 104-104 <= nums[i] <= 104numscontains distinct values sorted in ascending order.-104 <= target <= 104
Approach Overview
Problem Overview: You are given a sorted array of distinct integers and a target value. Return the index if the target exists. If not, return the index where it should be inserted to maintain sorted order.
Approach 1: Linear Scan (O(n) time, O(1) space)
The simplest idea is to iterate through the array from left to right and stop when you find the first element greater than or equal to the target. That index is either the position of the target or the correct insertion point. If the loop finishes without finding such an element, the target should be inserted at the end of the array. This approach is straightforward but inefficient for large inputs because it may require scanning the entire array.
Approach 2: Iterative Binary Search (O(log n) time, O(1) space)
The array is already sorted, which makes binary search the natural choice. Maintain two pointers left and right representing the current search range. Compute the middle index and compare nums[mid] with the target. If they match, return mid. If the target is larger, move left to mid + 1; otherwise move right to mid - 1. When the loop finishes, left will be the correct insertion position because it points to the first element greater than the target.
Approach 3: Recursive Binary Search (O(log n) time, O(log n) space)
This method applies the same binary search logic but expresses it through recursion. Each recursive call reduces the search range by half based on the comparison with the middle element. When the search interval becomes invalid (left > right), the correct insertion index is simply left. The algorithm still performs logarithmic comparisons, but recursion adds call stack overhead, giving it O(log n) auxiliary space.
Recommended for interviews: Interviewers expect the binary search solution because the array is sorted. Showing the linear scan first demonstrates baseline reasoning, but implementing the iterative binary search proves you recognize the sorted array → logarithmic search optimization. The iterative version is usually preferred over recursion since it avoids extra stack usage while keeping the same O(log n) performance.
Approach 1: Iterative Binary Search
The iterative binary search approach involves using two pointers, 'left' and 'right'. We continue dividing the array into halves until we locate the target or determine where it should be inserted. The algorithm compares the target with the middle element and appropriately adjusts the 'left' or 'right' pointer based on this comparison.
This solution uses a binary search to find the target. If the target is found, it returns the index. If not, it returns the position where the target should be inserted to maintain sorted order.
Complexity
Time Complexity: O(log n)
Space Complexity: O(1) since no extra space is used.
Approach 2: Recursive Binary Search
In this approach, the binary search is implemented recursively. The function calls itself with updated bounds until the target is found or until it determines the correct insertion index. This approach makes use of stack space due to recursion but is logically intuitive.
This C solution uses recursion to implement binary search to find the index or the prospective insertion position of the target.
Complexity
Time Complexity: O(log n)
Space Complexity: O(log n) due to recursion stack.
Approach 3: Binary Search
Since the array nums is already sorted, we can use the binary search method to find the insertion position of the target value target.
The time complexity is O(log n), and the space complexity is O(1). Here, n is the length of the array nums.
Code
Python
Java
C++
Go
TypeScript
Rust
JavaScript
PHP
Approach 4: Binary Search (Built-in Function)
We can also directly use the built-in function for binary search.
The time complexity is O(log n), where n is the length of the array nums. The space complexity is O(1).
Complexity Comparison
| Approach | Complexity |
|---|---|
| Iterative Binary Search | Time Complexity: O(log n) |
| Recursive Binary Search | Time Complexity: O(log n) |
| Binary Search | — |
| Binary Search (Built-in Function) | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Linear Scan | O(n) | O(1) | Quick baseline solution or when the array size is very small |
| Iterative Binary Search | O(log n) | O(1) | Best choice when the array is sorted and you need optimal performance |
| Recursive Binary Search | O(log n) | O(log n) | Useful for learning recursion or when implementing divide-and-conquer patterns |
Video Solution
Search Insert Position - Binary Search - Leetcode 35 - Python • NeetCode • 93,747 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Search Insert Position easy or hard?
Search Insert Position Python/Java solution
How to solve Search Insert Position in O(log n)?
What is the best approach for Search Insert Position?
Is Search Insert Position asked at Google/Amazon/Meta?
What data structure is used in Search Insert Position?
What is the time complexity of Search Insert Position?
Ready to solve this problem?
Practice Search Insert Position with our built-in code editor and test cases.
Practice on FleetCode