6. Search Insert Position
easyAsked at CoupangBinary-search for an insert index — Coupang uses this to test binary-search instincts that show up later in price-range filter problems.
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 if it were inserted in order. You must write an algorithm with O(log n) runtime.
Constraints
1 <= nums.length <= 10^4-10^4 <= nums[i] <= 10^4nums contains distinct values sorted ascending
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 pass 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
Classic lo/hi loop, return lo on miss.
- 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:
Coupang-specific tips
Coupang interviewers will probe whether you used the half-open interval pattern; that pattern is the house standard for their price-tier lookup.
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.