Search Insert Position (LC 35)
You have an array of distinct integers in sorted order and a target value. If target is already in the array, return its index; otherwise, return the index it would land at if you inserted it while keeping the array sorted.
Solve it in O(log n) time.
Worked Examples
nums = [1,3,5,6], target = 52nums = [1,3,5,6], target = 21nums = [1,3,5,6], target = 74⚖️Formal Constraints & Bounds
1 <= nums.length <= 104-104 <= nums[i] <= 104numscontains distinct values sorted in ascending order.-104 <= target <= 104
Core Insight
The predicate arr[mid] >= target transforms the sorted array into a boolean sequence [False, ..., False, True, ..., True]. Binary search finds the transition boundary.
Real-World Scenario & Production Applications
Database range index scans (e.g. WHERE timestamp >= '2026-08-01') use lower-bound binary search to locate the exact starting leaf page in logarithmic time.
Subproblems & Recurrence Decomposition3 Phases
Map the sorted array to a monotonic boolean sequence via predicate P(i) = (nums[i] >= target). Produces [False, False, ..., True, True] where the first True is our exact answer.
# Monotonic Predicate Partition:
# [False, False, ..., True, True]
P(mid) = (nums[mid] >= target)Step-by-Step Execution Trace Table
| Step | Search Window [lo, hi] | mid | nums[mid] | Predicate nums[mid] >= 8? | Action & State Update | Recorded first_true |
|---|---|---|---|---|---|---|
| 1 | [0, 6] | 3 | 7 | False (7 < 8) | Infeasible push right: lo = mid + 1 = 4 | — |
| 2 | [4, 6] | 5 | 13 | True (13 >= 8) | Feasible record 5, push left: hi = mid - 1 = 4 | 5 |
| 3 | [4, 4] | 4 | 11 | True (11 >= 8) | Feasible record 4, push left: hi = mid - 1 = 3 | 4 |
| 4 | [4, 3] | — | — | lo > hi (Window empty) | Loop terminates Return first_true = 4 | 4 |
| 1 | def is_feasible(i): |
| 2 | <the yes/no question about slot i> |
| 3 | lo, hi = 0, len(nums) |
| 4 | while lo < hi: |
| 5 | mid = lo + (hi - lo) // 2 |
| 6 | if is_feasible(mid): |
| 7 | hi = mid |
| 8 | else: |
| 9 | lo = mid + 1 |
| 10 | return lo |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Keeping a qualifying answer in play and deliberately continuing to search feels backwards the first time you see it — most searches stop the moment they find something. Here's why this one doesn't.
🎢 The Analogy: The Amusement Park Height Line
Imagine a line of kids sorted shortest to tallest, and a ride requires "at least 4 feet tall." You want the first kid in line who's tall enough — not just a tall-enough kid. If you jump into the middle of the line and find a kid who qualifies, you can't stop there: there might be a shorter (but still qualifying) kid standing earlier in line. So you keep that kid in the running (the stretch of line you still consider now ends at them) and keep checking further to the left. If a kid is too short, everyone before them is too short as well, so the stretch you consider now starts just after them. When that stretch shrinks to a single spot, it is the first qualifier (or the end of the line, if nobody qualifies).
🔑 The Key Idea in the Code
The predicate nums[mid] >= target is just "is this kid tall enough?" — a [False, False, ..., True, True] line by construction, because nums is sorted. Keeping mid with hi = mid instead of returning immediately is what separates "found a match" from "found the boundary."
Writing
lo = midinstead oflo = mid + 1Writing
hi = mid - 1in the half-open templateSetting
hito the last index, not one past itReading
nums[i]without checkingi < len(nums)Using a check that is not monotonic
Adding 1 to what
bisect_leftreturnsForgetting
+ loon thebisectform
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
"If target is already in the array, return its index; otherwise, return the index it would land at if you inserted it", on a sorted array: the insert position is the first index with nums[i] >= target (Lower Bound).
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: for Search Insert Position (LC 35), every index below lo has nums[i] < target and every index from hi on has nums[i] >= target (or is len(nums)), with lo, hi = 0, len(nums); the answer is lo when lo == hi.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
lo = midin the False branch: with the floor midpoint,mid == lowhen two candidates are left, so the loop never ends (nums = [1,3,5,6],target = 5stops atlo = 1,hi = 2).Starting
hiatlen(nums) - 1: atargetlarger than every value must returnlen(nums)(LeetCode Example 3,target = 7on[1,3,5,6]gives4), which that window can never produce.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I'd use Lower Bound.
nums[i] >= targetis False, then True, so the insert position is the first True. I starthiatlen(nums)so 'insert at the end' is a possible answer. Ifmidpasses the check it might be the answer, so I keep it withhi = mid; if it fails, the answer is strictly to its right, solo = mid + 1. The loop stops whenlo == hi, and that is the answer. The trap islo = mid: with two candidates left,midequalsloand the loop never moves. It'sO(log n)time andO(1)space."
Complexity & Mathematical Proof
O(log N)
Look at the while loop: while lo < hi:. In each step, we evaluate the monotonic boolean predicate nums[mid] >= target. If True, mid may be the first True, so we keep it with hi = mid; if False, we move right with lo = mid + 1. Either way the window [lo, hi) loses at least half of its size (rounded down), so from N candidates the loop runs at most ⌊log2 N⌋ + 1 times with O(1) work per step, yielding O(log N) time.
O(1)
Look at memory allocation: The loop is iterative with O(1) call stack. We store only three scalar integer variables (lo, hi, mid). Zero heap objects or arrays are allocated. Auxiliary space is O(1).
Derivation Progression
P(i) = (nums[i] ≥ target)
Sorted order guarantees P(i) is monotonically non-decreasing [False...False, True...True]. Binary search locates the exact boundary transition.
hi = mid, O(1)
When P(mid) is True, mid stays in the window as a possible answer and everything right of it is dropped.
at most ⌊log2 N⌋ + 1 steps ⟹ O(log N)
The window closes at lo == hi, which is the boundary.
Variable Definitions
Total number of elements in the sorted array
Memory Architecture & Bounds
O(1) Iterative while loop with zero recursion stack frames
O(1) Only scalar variables (lo, hi, mid)
O(1) Returns a single integer insertion index
Boundary Best / Worst Cases
when the array has 1 element; otherwise between and iterations, depending on the target.
.
— at most iterations until lo == hi.
Recurrence Tree Topology
Senior SWE Deconstruction & Hardware Caveats
The structural trigger that catches my eye is: "insertion point if the target is missing" — a target that's found returns its index, but one that's absent returns where it would slot in. Notice how this diverges from LC 704: we are no longer searching for an isolated value that permits early exit—we are searching for a transition frontier. The boolean predicate nums[i] >= target partitions the sorted array into two contiguous zones: [False, ..., False, True, ..., True]. This maps directly to Monotonic Predicate Boundary Search (lower bound / bisect_left).
The array length is with an requirement, demanding logarithmic bisection. The values are distinct and fit within standard integers (). The search runs on lo = 0 and hi = len(nums): hi starts one past the last index because a target greater than every element is inserted at index , so must stay a possible answer.
A target smaller than nums[0] needs no special case: every check is True, hi walks down to 0, and the loop returns 0.
Search Insert Position (LC 35)
You have an array of distinct integers in sorted order and a target value. If target is already in the array, return its index; otherwise, return the index it would land at if you inserted it while keeping the array sorted.
Solve it in O(log n) time.
Worked Examples
nums = [1,3,5,6], target = 52nums = [1,3,5,6], target = 21nums = [1,3,5,6], target = 74⚖️Formal Constraints & Bounds
1 <= nums.length <= 104-104 <= nums[i] <= 104numscontains distinct values sorted in ascending order.-104 <= target <= 104
Core Insight
The predicate arr[mid] >= target transforms the sorted array into a boolean sequence [False, ..., False, True, ..., True]. Binary search finds the transition boundary.
Real-World Scenario & Production Applications
Database range index scans (e.g. WHERE timestamp >= '2026-08-01') use lower-bound binary search to locate the exact starting leaf page in logarithmic time.
Subproblems & Recurrence Decomposition3 Phases
Map the sorted array to a monotonic boolean sequence via predicate P(i) = (nums[i] >= target). Produces [False, False, ..., True, True] where the first True is our exact answer.
# Monotonic Predicate Partition:
# [False, False, ..., True, True]
P(mid) = (nums[mid] >= target)Step-by-Step Execution Trace Table
| Step | Search Window [lo, hi] | mid | nums[mid] | Predicate nums[mid] >= 8? | Action & State Update | Recorded first_true |
|---|---|---|---|---|---|---|
| 1 | [0, 6] | 3 | 7 | False (7 < 8) | Infeasible push right: lo = mid + 1 = 4 | — |
| 2 | [4, 6] | 5 | 13 | True (13 >= 8) | Feasible record 5, push left: hi = mid - 1 = 4 | 5 |
| 3 | [4, 4] | 4 | 11 | True (11 >= 8) | Feasible record 4, push left: hi = mid - 1 = 3 | 4 |
| 4 | [4, 3] | — | — | lo > hi (Window empty) | Loop terminates Return first_true = 4 | 4 |
| 1 | def is_feasible(i): |
| 2 | <the yes/no question about slot i> |
| 3 | lo, hi = 0, len(nums) |
| 4 | while lo < hi: |
| 5 | mid = lo + (hi - lo) // 2 |
| 6 | if is_feasible(mid): |
| 7 | hi = mid |
| 8 | else: |
| 9 | lo = mid + 1 |
| 10 | return lo |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Keeping a qualifying answer in play and deliberately continuing to search feels backwards the first time you see it — most searches stop the moment they find something. Here's why this one doesn't.
🎢 The Analogy: The Amusement Park Height Line
Imagine a line of kids sorted shortest to tallest, and a ride requires "at least 4 feet tall." You want the first kid in line who's tall enough — not just a tall-enough kid. If you jump into the middle of the line and find a kid who qualifies, you can't stop there: there might be a shorter (but still qualifying) kid standing earlier in line. So you keep that kid in the running (the stretch of line you still consider now ends at them) and keep checking further to the left. If a kid is too short, everyone before them is too short as well, so the stretch you consider now starts just after them. When that stretch shrinks to a single spot, it is the first qualifier (or the end of the line, if nobody qualifies).
🔑 The Key Idea in the Code
The predicate nums[mid] >= target is just "is this kid tall enough?" — a [False, False, ..., True, True] line by construction, because nums is sorted. Keeping mid with hi = mid instead of returning immediately is what separates "found a match" from "found the boundary."
Writing
lo = midinstead oflo = mid + 1Writing
hi = mid - 1in the half-open templateSetting
hito the last index, not one past itReading
nums[i]without checkingi < len(nums)Using a check that is not monotonic
Adding 1 to what
bisect_leftreturnsForgetting
+ loon thebisectform
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
"If target is already in the array, return its index; otherwise, return the index it would land at if you inserted it", on a sorted array: the insert position is the first index with nums[i] >= target (Lower Bound).
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: for Search Insert Position (LC 35), every index below lo has nums[i] < target and every index from hi on has nums[i] >= target (or is len(nums)), with lo, hi = 0, len(nums); the answer is lo when lo == hi.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
lo = midin the False branch: with the floor midpoint,mid == lowhen two candidates are left, so the loop never ends (nums = [1,3,5,6],target = 5stops atlo = 1,hi = 2).Starting
hiatlen(nums) - 1: atargetlarger than every value must returnlen(nums)(LeetCode Example 3,target = 7on[1,3,5,6]gives4), which that window can never produce.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I'd use Lower Bound.
nums[i] >= targetis False, then True, so the insert position is the first True. I starthiatlen(nums)so 'insert at the end' is a possible answer. Ifmidpasses the check it might be the answer, so I keep it withhi = mid; if it fails, the answer is strictly to its right, solo = mid + 1. The loop stops whenlo == hi, and that is the answer. The trap islo = mid: with two candidates left,midequalsloand the loop never moves. It'sO(log n)time andO(1)space."
Complexity & Mathematical Proof
O(log N)
Look at the while loop: while lo < hi:. In each step, we evaluate the monotonic boolean predicate nums[mid] >= target. If True, mid may be the first True, so we keep it with hi = mid; if False, we move right with lo = mid + 1. Either way the window [lo, hi) loses at least half of its size (rounded down), so from N candidates the loop runs at most ⌊log2 N⌋ + 1 times with O(1) work per step, yielding O(log N) time.
O(1)
Look at memory allocation: The loop is iterative with O(1) call stack. We store only three scalar integer variables (lo, hi, mid). Zero heap objects or arrays are allocated. Auxiliary space is O(1).
Derivation Progression
P(i) = (nums[i] ≥ target)
Sorted order guarantees P(i) is monotonically non-decreasing [False...False, True...True]. Binary search locates the exact boundary transition.
hi = mid, O(1)
When P(mid) is True, mid stays in the window as a possible answer and everything right of it is dropped.
at most ⌊log2 N⌋ + 1 steps ⟹ O(log N)
The window closes at lo == hi, which is the boundary.
Variable Definitions
Total number of elements in the sorted array
Memory Architecture & Bounds
O(1) Iterative while loop with zero recursion stack frames
O(1) Only scalar variables (lo, hi, mid)
O(1) Returns a single integer insertion index
Boundary Best / Worst Cases
when the array has 1 element; otherwise between and iterations, depending on the target.
.
— at most iterations until lo == hi.
Recurrence Tree Topology
Senior SWE Deconstruction & Hardware Caveats
The structural trigger that catches my eye is: "insertion point if the target is missing" — a target that's found returns its index, but one that's absent returns where it would slot in. Notice how this diverges from LC 704: we are no longer searching for an isolated value that permits early exit—we are searching for a transition frontier. The boolean predicate nums[i] >= target partitions the sorted array into two contiguous zones: [False, ..., False, True, ..., True]. This maps directly to Monotonic Predicate Boundary Search (lower bound / bisect_left).
The array length is with an requirement, demanding logarithmic bisection. The values are distinct and fit within standard integers (). The search runs on lo = 0 and hi = len(nums): hi starts one past the last index because a target greater than every element is inserted at index , so must stay a possible answer.
A target smaller than nums[0] needs no special case: every check is True, hi walks down to 0, and the loop returns 0.