6. Search Insert Position
easyAsked at RobloxFind the index where a target would be inserted in a sorted array.
By Sam K., Founder, InterviewChamp.AI · Last verified
Problem
Given a sorted array of distinct integers and a target value, return its index if found. If not, return the index where it would be inserted to keep the array sorted. The algorithm must run in O(log n) time.
Constraints
1 <= nums.length <= 10^4Distinct sorted ascending-10^4 <= target <= 10^4
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 first element >= 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 search returning the insertion index when not found.
- 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:
Roblox-specific tips
Roblox uses binary search to probe whether you can hold loop invariants under stress — a key skill when implementing matchmaking tier insertion.
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.