Search Insert Position
Problem Statement
You are given an array nums of distinct numbers sorted from smallest to largest, and a number target.
If target is in the array, return its index. If it isn't, return the index where it would be inserted to keep the array sorted.
Your solution must run in O(log n) time.
A sorted integer array nums with distinct values, and an integer target.
The index of target if it's present; otherwise the index where it would go so the array stays sorted.
5 is already in the array, at index 2.
2 is missing. It belongs between 1 and 3, which is index 1.
7 is bigger than everything, so it goes at the very end: index 4 (= the array's length).
- • 1 ≤ nums.length ≤ 10^4
- • −10^4 ≤ nums[i] ≤ 10^4
- • nums contains distinct values sorted in ascending order
- • −10^4 ≤ target ≤ 10^4
Pattern Recognition Clues
Recognising these key signals in the problem description immediately identifies the pattern:
Approach Complexity Ladder
Walk left to right; return the first index with nums[i] ≥ target
Binary search for the boundary; when the loop ends, lo is the answer
Go through the array from the left. The first element that is ≥ target is exactly the answer: either it is the target, or it's the first element bigger than it, so the target belongs right there. If no element is ≥ target, return n.
Recognition rule for this sub-pattern:
Unlock Complete Visual Walkthrough & Optimal C++
The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.
First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.
How this concept connects to System Design & C++ Systems
Top engineering interviews test whether you understand how algorithms like Binary Search translate into production architectures and low-level memory mechanics.