6. Search Insert Position
easyAsked at GitLabFind the index where a target should be inserted in a sorted array.
By Sam K., Founder, InterviewChamp.AI · Last verified
Problem
Given a sorted distinct integer array nums and a target, return the index where target is found or where it would be inserted to keep order. Must run in O(log n).
Constraints
1 <= nums.length <= 10^4Distinct valuesO(log n)
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 until you find 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 lo/hi loop; return lo at end.
- Time
- O(log n)
- Space
- O(1)
function searchInsert(nums, target){
let lo=0, hi=nums.length;
while (lo<hi){
const m=(lo+hi)>>1;
if (nums[m]<target) lo=m+1; else hi=m;
}
return lo;
}Tradeoff:
GitLab-specific tips
GitLab interviewers love when you draw the invariant for [lo, hi) on the whiteboard before coding — they grade rigor over speed.
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.