How do you solve Search Insert Position?

Implement a binary search with left initialized to 0 and right to len(nums). While left = target, move right to mid to search the left half; else, move left to mid + 1 to search the right half. When the loop ends, left is the correct insertion index.

Search Insert Position

Q: What is the time complexity of Search Insert Position?

O(log n). Each iteration halves the search space by adjusting left or right pointers, resulting in logarithmic time relative to the array size.

Q: What pattern does Search Insert Position use?

The Pattern: Modified Binary Search (Lower Bound Search) The Heuristic: When searching for the insertion position in a sorted array, use binary search to find the smallest index where the element is greater than or equal to the target by adjusting the search boundaries based on comparisons, ensuring O(log n) time.

Easy Modified Binary Search

Problem

Given a sorted array of distinct integers nums and a target value target, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

1 ≤ nums.length ≤ 10⁴
−10⁴ ≤ nums[i] ≤ 10⁴
nums contains distinct values sorted in ascending order
−10⁴ ≤ target ≤ 10⁴

Example

Input: nums = [1,3,5,6], target = 5

Output: 2

The algorithm performs a binary search over the interval [0, 4). It first computes mid = 2. Since nums[2] = 5 which is greater than or equal to the target, the search narrows to the left half by setting right = mid. The process continues until left and right converge to index 2, which is the correct position of the target.

Approach

Straightforward Solution

A linear scan through the array to find the first element greater than or equal to the target would be O(n), which is inefficient for large arrays.

Core Observation

The problem reduces to finding the first index where nums[index] is greater than or equal to the target. This is the classic lower-bound search problem on a sorted array.

Path to Optimal

Preview

Recognizing the sorted nature of nums allows the use of binary search to find the target or its insertion point in O(log n) time…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Implement a binary search with left initialized to 0 and right to len(nums). While left < right, compute mid = (left + right) // 2…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(log n)

Each iteration halves the search space by adjusting left or right pointers, resulting in logarithmic time relative to the array size.

Space

O(1)

Only a fixed number of variables (left, right, mid) are used, with no additional data structures, resulting in constant auxiliary space.

Pattern Spotlight

Modified Binary Search (Lower Bound Search)

When searching for the insertion position in a sorted array, use binary search to find the smallest index where the element is greater than or equal to the target by adjusting the search boundaries based on comparisons, ensuring O(log n) time.

Solution

Python

1class Solution:
2    def searchInsert(self, nums: List[int], target: int) -> int:
3
4        left = 0
5        right = len(nums)
6
7        while left < right:
8
9            mid = (left + right) // 2
10
11            if nums[mid] >= target:   
12                right = mid
13            else:                    
14                left = mid + 1
15
16        return left

Step-by-Step Solution

Initialize Search Boundaries to Cover Entire Array

4left = 0
5right = len(nums)

Objective

To set the initial search window covering the entire array for binary search.

Key Insight

Setting left to 0 and right to len(nums) defines a half-open interval [left, right) that includes all valid insertion positions, including the position after the last element. This setup allows the binary search to correctly handle cases where the target is greater than all elements.

Interview Quick-Check

Core Logic

Initializing right to len(nums) instead of len(nums) - 1 allows the search to consider insertion at the end of the array.

State & Boundaries

The search interval is half-open [left, right), which simplifies boundary conditions and loop termination.

Narrow Search Window Using Binary Search to Find Target or Insertion Point

To iteratively reduce the search space by comparing the middle element to the target and adjusting boundaries accordingly.

Return the Computed Insertion Index

To output the final position where the target is or should be inserted.

2 more steps with full analysis available on Pro.

Line Analysis

This solution has 4 Critical lines interviewers watch for.

Line 16 Critical

return left

Return the insertion index after the search completes.

Returning left provides the smallest index where the target fits, satisfying the problem's requirement for both found and not found cases.

Line 11 Critical

if nums[mid] >= target:

Check if the middle element is greater than or equal to the target.

This comparison determines whether the target lies to the left (including mid) or to the right of mid, guiding the boundary adjustment.

Line 12 Critical

right = mid

Move the right pointer to mid so the search continues in the left half including mid.

When nums[mid] is greater than or equal to the target, the correct position could be mid itself. Moving right to mid keeps mid inside the search interval so the algorithm does not skip the potential answer while still shrinking the search space.

Full line-by-line criticality + rationale for all 9 lines available on Pro.

Test Your Understanding

Why does the algorithm return left at the end of the binary search loop?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Search Insert Position from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Search Insert Position drill

or drill a free problem

1	`class Solution:`
2	`def searchInsert(self, nums: List[int], target: int) -> int:`
3
4	`left = 0`
5	`right = len(nums)`
6
7	`while left < right:`
8
9	`mid = (left + right) // 2`
10
11	`if nums[mid] >= target:`
12	`right = mid`
13	`else:`
14	`left = mid + 1`
15
16	`return left`