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 it does not exist, return the index where it should be inserted to keep the array sorted.
Approach 1: Linear Scan (O(n) time, O(1) space)
Walk through the array from left to right and compare each element with the target. The first element greater than or equal to the target gives the correct insertion index. If you reach the end without finding such an element, the target belongs at index n. This works because the array is already sorted. The downside is the O(n) time complexity, which becomes inefficient for large inputs.
Approach 2: Iterative Binary Search (O(log n) time, O(1) space)
The sorted property allows you to use binary search. Maintain two pointers left and right. Compute mid and compare nums[mid] with the target. If equal, return mid. If the target is smaller, move the right boundary. If larger, move the left boundary. When the loop ends, left represents the exact insertion position. This works because binary search narrows the valid region where the target could appear while preserving sorted order in the array.
Approach 3: Recursive Binary Search (O(log n) time, O(log n) space)
The same binary search logic can be implemented recursively. Each recursive call processes half of the remaining range. The base case occurs when the search boundaries cross; at that point the left pointer indicates where the target should be inserted. This version is often easier to reason about conceptually, but recursion introduces O(log n) stack space due to the call stack.
Recommended for interviews: Iterative binary search. Interviewers expect you to recognize that the input is sorted and immediately apply binary search for O(log n) time. Starting with the linear scan demonstrates baseline reasoning, but implementing binary search correctly shows strong algorithm fundamentals and familiarity with classic search patterns.
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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(log n)
Space Complexity: O(log n) due to recursion stack.
| Approach | Complexity |
|---|---|
| Iterative Binary Search | Time Complexity: O(log n) |
| Recursive Binary Search | Time Complexity: O(log n) |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Linear Scan | O(n) | O(1) | Simple baseline solution or very small arrays |
| Iterative Binary Search | O(log n) | O(1) | Best choice when the array is sorted and large |
| Recursive Binary Search | O(log n) | O(log n) | When recursion is preferred for clarity or teaching binary search |
BS-2. Implement Lower Bound and Upper Bound | Search Insert Position | Floor and Ceil • take U forward • 443,441 views views
Watch 9 more video solutions →Practice Search Insert Position with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor