6. Search Insert Position
easyAsked at CircleCIFind the index where a target would be inserted in a sorted array to keep it sorted.
By Sam K., Founder, InterviewChamp.AI · Last verified
Problem
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 inserted in order. You must write an algorithm with O(log n) runtime complexity.
Constraints
1 <= nums.length <= 10^4-10^4 <= nums[i] <= 10^4nums sorted ascending, distinct
Examples
Example 1
Input
nums = [1,3,5,6], target = 5Output
2Example 2
Input
nums = [1,3,5,6], target = 2Output
1Approaches
1. Linear scan
Walk left-to-right and return the first index >= target.
- Time
- O(n)
- Space
- O(1)
for (let i = 0; i < nums.length; i++) {
if (nums[i] >= target) return i;
}
return nums.length;Tradeoff:
2. Binary search
Standard lower_bound style binary search; the final lo is the insertion point.
- Time
- O(log n)
- Space
- O(1)
function searchInsert(nums, target) {
let lo = 0, hi = nums.length;
while (lo < hi) {
const mid = (lo + hi) >> 1;
if (nums[mid] < target) lo = mid + 1;
else hi = mid;
}
return lo;
}Tradeoff:
CircleCI-specific tips
CircleCI graders will dock you for sloppy binary-search bounds — they review log-search code in the scheduler hot path frequently.
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.