Find First and Last Position

medium

Given a sorted array, find the starting and ending position of a target value. Return [-1, -1] if not found

Find First and Last Position

Key Insight

Run binary search twice: left-biased keeps searching left after finding target, right-biased keeps searching right.

Step 1Setup
Target: 8Phase 1: Find first occurrence
L
R
5
0
7
1
7
2
8
3
8
4
10
5
Search space: [0..5]

Find first and last occurrence of 8 in sorted array.

1 / 7

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: Find First and Last Position

Run binary search twice: left-biased keeps searching left after finding target, right-biased keeps searching right.

  1. Setup

    Find first and last occurrence of 8 in sorted array.

  2. Find First: Mid=2

    arr[2]=7 < 8, search right.

  3. Find First: Mid=4

    arr[4]=8 = target! But keep searching LEFT for earlier occurrence.

  4. Find First: Result

    right=3, mid=3, arr[3]=8 = target. left=3, right=2. First occurrence at index 3.

  5. Find Last: Reset

    Start Phase 2. left=0, right=5. Now search right-biased.

  6. Find Last: Mid=4

    arr[4]=8 = target! Keep searching RIGHT for later occurrence.

  7. Result

    First at 3, Last at 4.