Skip to content

34. Find First and Last Position of Element in Sorted Array

Edited by Charles

Medium · Python · Array

Problem

Read the original problem on LeetCode.

The official page contains the problem statement, examples, and constraints.

Explanation, examples & other approaches

Core idea

Use Binary Search twice:

Find the leftmost occurrence of target. Find the rightmost occurrence of target.

Original study notes follow, including intermediate snippets and earlier attempts.

Idea

Use Binary Search twice:

  1. Find the leftmost occurrence of target.
  2. Find the rightmost occurrence of target.

The key difference from normal binary search is:

When target is found, do not immediately return. Continue searching for the boundary.

Find the Left Boundary

Use standard binary search:

left, right = 0, len(nums) - 1

If:

nums[mid] == target

record the current position:

res = mid

But this may not be the first occurrence.

For example:

nums = [5, 7, 7, 8, 8, 10]
                    ↑
                   mid

Even if we find 8 at index 4, there may still be another 8 on the left.

Therefore:

res = mid
right = mid - 1

This means:

Found target
    ↓
Record current index
    ↓
Continue searching left

So for the left boundary:

nums[mid] == target
→ save mid
→ move right to mid - 1

Find the Right Boundary

The logic is symmetric.

If:

nums[mid] == target

record the position:

res = mid

Then continue searching to the right:

left = mid + 1

because there may be another occurrence of target later in the array.

So for the right boundary:

nums[mid] == target
→ save mid
→ move left to mid + 1

Example

nums = [5, 7, 7, 8, 8, 10]
target = 8

The target range is:

index:  0  1  2  3  4   5
nums:   5  7  7  8  8  10
                  ↑  ↑
                left right

Left Boundary

Suppose binary search finds an 8.

Instead of returning immediately:

res = mid
right = mid - 1

Continue searching the left half until no earlier 8 exists.

Result:

left boundary = 3

Right Boundary

When an 8 is found:

res = mid
left = mid + 1

Continue searching the right half until no later 8 exists.

Result:

right boundary = 4

Therefore:

[3, 4]

If Target Does Not Exist

Initialize:

res = -1

If target is never found, res remains -1.

For example:

nums = [5, 7, 7, 8, 8, 10]
target = 6

Neither binary search finds 6, so:

[-1, -1]

Normal binary search:

nums[mid] == target
→ return mid

LeetCode 34:

Find left boundary:

nums[mid] == target
→ record mid
→ continue left

Find right boundary:

nums[mid] == target
→ record mid
→ continue right

The most important idea is:

Finding target ≠ finding the boundary

We must continue binary search after finding target.

Complexity

We perform binary search twice.

Time Complexity:

O(log n)

because:

O(log n) + O(log n) = O(log n)

Space Complexity:

O(1)
Study record
Field Value
Attempts 1
Mastery ❚
The Latest Attempt September 8, 2026

Python solution

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:

        def findLeft():
            left, right = 0, len(nums) - 1
            res = -1

            while left <= right:
                mid = (left + right) // 2

                if nums[mid] == target:
                    res = mid
                    right = mid - 1
                elif nums[mid] < target:
                    left = mid + 1
                else:
                    right = mid - 1

            return res

        def findRight():
            left, right = 0, len(nums) - 1
            res = -1

            while left <= right:
                mid = (left + right) // 2

                if nums[mid] == target:
                    res = mid
                    left = mid + 1
                elif nums[mid] < target:
                    left = mid + 1
                else:
                    right = mid - 1

            return res

        return [findLeft(), findRight()]

Back to Bonus Array · All Algorithm notes