6. Search Insert Position
easyAsked at TripAdvisorFind the index of a target in a sorted array, or where it would be inserted.
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], target <= 10^4nums sorted ascending, no duplicates
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 until value >= 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 low/high bounds; on miss, lo is the insert 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:
TripAdvisor-specific tips
TripAdvisor uses binary-search variants when slotting new reviews or price tiers into already-sorted backing arrays.
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.