Leetcode 34: Find First and Last Position of Element in Sorted Array

 

1. Problem Statement (Simple Explanation):

You’re given:

• A sorted array nums in non-decreasing order.

• An integer target.

You must:

• Return a 2-element array [firstIndex, lastIndex] where:

• firstIndex = index of the first occurrence of target

• lastIndex = index of the last occurrence of target

• If target is not present, return [-1, -1].

You must use an O(log n) algorithm → binary search.

2. Examples:

Example 1:

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

8 appears at indices 3 and 4.

Output: [3, 4]

Example 2:

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

6 is not present.

Output: [-1, -1]

Example 3:

Input: nums = [], target = 0

Empty array.

Output: [-1, -1]

3. Approach – Two Binary Searches (Lower Bound & Upper Bound):

We’ll do two modified binary searches:

1. findFirst – find the leftmost index where nums[i] == target.

2. findLast – find the rightmost index where nums[i] == target.

Find First Occurrence:

We want the smallest index i such that nums[i] >= target and nums[i] == target.

Binary search:

• left = 0, right = n - 1, first = -1.

• While left <= right:

• mid = left + (right - left) / 2

• If nums[mid] == target:

• Save first = mid

• Move right = mid - 1 to search further left

• Else if nums[mid] < target:

• Move right: left = mid + 1

• Else (nums[mid] > target):

• Move left: right = mid - 1

At the end, first is index of first occurrence or -1 if not found.

Find Last Occurrence::

We want the largest index i such that nums[i] <= target and nums[i] == target.

Binary search:

• left = 0, right = n - 1, last = -1.

• While left <= right:

• mid = left + (right - left) / 2

• If nums[mid] == target:

• Save last = mid

• Move left = mid + 1 to search further right

• Else if nums[mid] < target:

• Move right: left = mid + 1

• Else:

• Move left: right = mid - 1

At the end, last is index of last occurrence or -1.

Final Answer:

• Compute first = findFirst(nums, target)

• If first == -1: return [-1, -1] (target not present).

• Else compute last = findLast(nums, target)

• Return [first, last].

Pseudo-code:

Complexity:

• Each binary search: O(logn)

• Two searches: still O(logn)

• Extra space: O(1)

4. Java code:

5. C code:

6. C++ code:

7. Python code:

8. JavaScript code: