Skip to main content

35. Search Insert Position

easyAsked at JPMorgan

Given a sorted array and a target, return the index where target is found, or the index at which it would be inserted. JPMorgan asks this on Software Engineer Programme phone screens to verify clean binary-search bounds reasoning before moving to harder follow-ups.

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

Source citations

Public interview reports confirming this problem appears in JPMorgan loops.

  • Glassdoor (2026-Q1)— JPMorgan SDE phone-screen reports list this as the standard binary-search warm-up.
  • LeetCode (2026-Q1)— Tagged JPMorgan on the LeetCode company tag page.
  • Reddit r/cscareerquestions (2025-09)— JPMC SWE-I write-up: 'search insert position, then asked about finding the leftmost duplicate'.

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 left-to-right; return the first index where nums[i] >= target. Return n if none.

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

Tradeoff: Trivially correct but explicitly fails the O(log n) constraint. Useful only as a baseline.

2. Binary search for lower bound (optimal)

Find the leftmost index i with nums[i] >= target. Standard lower-bound binary search.

Time
O(log n)
Space
O(1)
function searchInsert(nums, target) {
  let lo = 0;
  let hi = nums.length;
  while (lo < hi) {
    const m = (lo + hi) >> 1;
    if (nums[m] < target) lo = m + 1;
    else hi = m;
  }
  return lo;
}

Tradeoff: O(log n) — the answer JPMorgan interviewers expect. The hi = nums.length (not length - 1) and the lo < hi (not lo <= hi) are the deliberate choices that make this a lower-bound search rather than equality search; mention them by name.

JPMorgan-specific tips

JPMorgan interviewers grade binary-search hygiene: (1) which variant are you writing — equality, lower bound, upper bound? (lower bound here); (2) is hi inclusive or exclusive? (exclusive — start at nums.length); (3) when do you stop — lo < hi for exclusive hi. State all three before coding so the interviewer sees you understand the template, not just this instance.

Common mistakes

  • Initialising hi = nums.length - 1 — would not return n when target is larger than every element.
  • Using lo <= hi with exclusive hi — risks infinite loop or off-by-one.
  • Computing the middle as (lo + hi) / 2 in languages with integer overflow risk — use lo + ((hi - lo) >> 1) defensively.
  • Returning m instead of lo at the end — m is the last midpoint checked, not the answer.

Follow-up questions

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

  • Find First and Last Position of Element in Sorted Array (LC 34) — two lower-bound searches.
  • Find Peak Element (LC 162) — binary search on a non-monotonic predicate.
  • Search in Rotated Sorted Array (LC 33) — binary search with rotation.
  • What if there are duplicates? Find the leftmost vs rightmost occurrence (LC 34).

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 exclusive hi (nums.length) and lo < hi?

Lower-bound binary search returns a valid index in [0, n]. With exclusive hi the loop variant lo == hi at termination naturally represents the insert position even when target is larger than every element. Inclusive hi (nums.length - 1) cannot represent the after-the-end position without an extra check.

How does this generalise to the duplicate-handling variants?

Lower-bound finds the leftmost index with nums[i] >= target. Upper-bound (else branch becomes nums[m] <= target -> lo = m + 1) finds the leftmost index with nums[i] > target. Together they give the [first, last+1) range of duplicates of target in O(log n). LC 34 is exactly this.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →