Search Insert Position

easy

Given a sorted array and a target, return the index if found or where it would be inserted to keep sorted order

Search Insert Position

Key Insight

When target is not found, left pointer lands exactly at the insertion point.

Step 1Initialize
Target: 2
L
R
1
0
3
1
5
2
6
3
Search space: [0..3]

left=0, right=3. Searching for 2.

1 / 5

Learn the Pattern

Binary SearchEliminate half the search space each iteration by comparing the midpoint against a condition, reducing O(n) linear scans to O(log n).
Practice the Code

Step-by-Step Walkthrough: Search Insert Position

When target is not found, left pointer lands exactly at the insertion point.

  1. Initialize

    left=0, right=3. Searching for 2.

  2. First Mid

    mid=1, arr[1]=3. 3 > 2, search left.

  3. Narrow Left

    right=0, mid=0, arr[0]=1. 1 < 2, search right.

  4. Loop Ends

    left=1, right=0. left > right, loop exits. left=1 is insertion point.

  5. Result

    Insert 2 at index 1 to maintain sorted order: [1, 2, 3, 5, 6]