Skip to main content

6. Search Insert Position

easyAsked at PayPal

Given a sorted array and a target, return the index where target is found, or where it would be inserted to keep the array sorted. PayPal asks this to test whether you can write a bug-free binary search — the foundation for fast lookups in their sorted fraud-rule index.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in PayPal loops.

  • Blind (2025-11)— PayPal phone-screen variant — interviewer pushes for O(log n).

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 complexity.

Constraints

  • 1 <= nums.length <= 10^4
  • -10^4 <= nums[i] <= 10^4
  • nums contains distinct values sorted in ascending order.
  • -10^4 <= target <= 10^4

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

Example 3

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

Approaches

1. Linear scan

Walk until you find target or an element greater than it.

Time
O(n)
Space
O(1)
function searchInsert(nums, target) {
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] >= target) return i;
  }
  return nums.length;
}

Tradeoff: Violates the O(log n) requirement explicitly stated in the problem.

2. Binary search lower-bound (optimal)

Standard binary search. When loop exits, lo points to the insertion index.

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: Classic lower-bound binary search. Same primitive PayPal uses to index into their sorted fraud-rule table by transaction amount.

PayPal-specific tips

PayPal wants the lower-bound variant — hi = nums.length (exclusive), not nums.length - 1. Bonus signal: discuss overflow safety — use `(lo + hi) >>> 1` in JS or `lo + ((hi - lo) >> 1)` to avoid the classic Java-int-overflow bug on huge arrays.

Common mistakes

  • Using `hi = nums.length - 1` and `lo <= hi` — works but mis-handles the insert-at-end case unless you add a special check.
  • Integer overflow on `(lo + hi) / 2` — use the bit shift or the diff form.
  • Returning -1 when not found instead of the insertion index.

Follow-up questions

An interviewer at PayPal may pivot to one of these next:

  • What if duplicates are allowed — find first/last occurrence (LC 34).
  • Search in rotated sorted array (LC 33).
  • Find peak element (LC 162).

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why hi = nums.length, not nums.length - 1?

Using length-as-exclusive bound lets you express 'insert at the end' without a special case. The loop invariant 'answer is in [lo, hi)' stays clean.

Why `>> 1` instead of `/ 2`?

Bit shift is exact integer division and avoids any float weirdness. In other languages it also avoids the `(lo + hi)` overflow trap on 32-bit int.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →