6. Search Insert Position
easyAsked at NubankFind the correct insertion index for a new credit-score tier into a sorted threshold table.
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 run in O(log n).
Constraints
1 <= nums.length <= 10^4Distinct sorted ints
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 an 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
Classic left-bound binary search; lo ends at insertion position.
- 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:
Nubank-specific tips
Nubank wants you to write the half-open `[lo, hi)` invariant explicitly — sloppy binary search bugs silently misprice risk-tier lookups.
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.