Search Insert Position

Search Insert Position

What is this problem about?

The Search Insert Position interview question gives you a sorted array of distinct integers and a target value. Your task is to find the index where the target exists in the array. If it does not exist, return the index at which it would need to be inserted to keep the array sorted. This is a foundational binary search problem with a clean, practical outcome.

Why is this asked in interviews?

Apple, Uber, Microsoft, Meta, Amazon, Google, Bloomberg, and Adobe ask this problem as a binary search fundamentals check. It tests whether candidates can implement clean binary search with precise boundary conditions. The insertion-position variant — where a missing target still has a meaningful answer — is a stepping stone to harder problems like Find First and Last Position and lower_bound/upper_bound in sorted containers. It also appears in competitive programming, database index lookups, and autocomplete ranking systems.

Algorithmic pattern used

The pattern is standard binary search with an insertion fallback. Initialize left = 0, right = len(nums) - 1. While left <= right, compute mid = (left + right) // 2. If nums[mid] == target, return mid. If nums[mid] < target, set left = mid + 1. If nums[mid] > target, set right = mid - 1. After the loop, left holds the correct insertion position — this is the key insight: when the loop ends, left is always where the target would be inserted.

Example explanation

Array: [2, 5, 8, 12, 17], target = 9.

• left=0, right=4. mid=2. nums[2]=8 < 9 → left=3.
• left=3, right=4. mid=3. nums[3]=12 > 9 → right=2.
• left=3 > right=2. Exit.

Return left = 3. (9 would be inserted between 8 and 12 at index 3.)

Target = 5: mid=2 (8>5)→right=1; mid=0 (2<5)→left=1; mid=1 (5==5) → return 1.

Common mistakes candidates make

• Using left < right instead of left <= right, which can miss the exact target match when one element remains.
• Not returning left after the loop — some candidates return -1 or some default, failing the insertion-position requirement.
• Using integer overflow-prone (left + right) / 2 instead of left + (right - left) / 2 in languages like C/Java.
• Confusing this problem with the variant that allows duplicates — this version guarantees all values are distinct.

Interview preparation tip

For the Search Insert Position coding problem, the binary search array interview pattern is the fundamental skill to internalize. The key takeaway: after a binary search loop that uses left <= right, the variable left always lands at the correct insertion position for a missing target. This property is used in C++ std::lower_bound and Python's bisect_left. Practice articulating this termination invariant to interviewers at Apple and Instacart — it shows deep understanding of binary search mechanics beyond just the happy-path case.