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] <= 104nums contains distinct values sorted in ascending order.-104 <= target <= 104Problem 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.
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.
Time Complexity: O(log n)
Space Complexity: O(1) since no extra space is used.
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.
Time Complexity: O(log n)
Space Complexity: O(log n) due to recursion stack.
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.
Python
Java
C++
Go
TypeScript
Rust
JavaScript
PHP
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).
| 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) | — |
| 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 |
Search Insert Position - Binary Search - Leetcode 35 - Python • NeetCode • 89,929 views views
Watch 9 more video solutions →Practice Search Insert Position with our built-in code editor and test cases.
Practice on FleetCode