Skip to main content

6. Search Insert Position

easyAsked at TripAdvisor

Find the index of a target in a sorted array, or where it would be inserted.

By Alex Chen, 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^4
  • nums sorted ascending, no duplicates

Examples

Example 1

Input
nums = [1,3,5,6], target = 5
Output
2

Example 2

Input
nums = [1,3,5,6], target = 2
Output
1

Approaches

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.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill Search Insert Position and other TripAdvisor interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →