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

Problem Statement

You are given an array of integers nums sorted in non-decreasing order and a target value target. Your task is to find the starting and ending position of the given target in the array. If the target is not present, return [-1, -1].

Example Inputs, Outputs, and Explanations

1. Example 1

   • Input: nums = [5,7,7,8,8,10], target = 8
   • Output: [3,4]
   • Explanation: The target value 8 appears at indices 3 and 4.

2. Example 2

   • Input: nums = [5,7,7,8,8,10], target = 6
   • Output: [-1,-1]
   • Explanation: The target value 6 is not present in the array.

3. Example 3

   • Input: nums = [], target = 0
   • Output: [-1,-1]
   • Explanation: The array is empty, so the target cannot be found.

Constraints

• The array nums is sorted in non-decreasing order.
• The length of nums is between 0 and 10^5.
• Each element in nums is an integer.
• The target is an integer.

Hints

• Hint 1:
  Since the array is sorted, think about using binary search to find the target. A standard binary search finds one occurrence, but you need to find the boundaries (first and last positions).

• Hint 2:
  Modify binary search to find the left boundary (first occurrence) and then separately find the right boundary (last occurrence). Focus on moving the search boundaries even when you find the target.

Approaches to Solve the Problem

Approach 1: Brute Force (Linear Scan)

Idea

• Traverse the array from start to end.
• Record the first and last positions when you encounter the target.

Steps

1. Initialize first to -1 and last to -1.
2. Iterate over the array:
   • When you see the target for the first time, update first.
   • Keep updating last whenever you see the target.
3. Return [first, last].

Drawbacks

• Time Complexity: O(n) – acceptable for small arrays but not optimal for large arrays.

Approach 2: Optimal Binary Search

Idea

• Use binary search twice:
  • Left Boundary Search: Find the first occurrence by moving the high pointer even if you find the target.
  • Right Boundary Search: Find the last occurrence by moving the low pointer even if you find the target.

Detailed Steps

1. Find Left Boundary:
   • Initialize left to 0 and right to n - 1.
   • While left <= right:
     • Compute mid = (left + right) // 2.
     • If nums[mid] is less than the target, move left to mid + 1.
     • Otherwise, move right to mid - 1.
   • After the loop, left should point to the first occurrence if it exists.
2. Find Right Boundary:
   • Reinitialize left to 0 and right to n - 1.
   • While left <= right:
     • Compute mid = (left + right) // 2.
     • If nums[mid] is greater than the target, move right to mid - 1.
     • Otherwise, move left to mid + 1.
   • After the loop, right should point to the last occurrence if it exists.
3. Validation:
   • Verify that the found positions are within array bounds and that the target is indeed present.

Advantages

• Time Complexity: O(log n) for each binary search, so overall O(log n).
• Space Complexity: O(1).

Step-by-Step Walkthrough with Visual Example

Consider nums = [5, 7, 7, 8, 8, 10] and target = 8.

Finding the Left Boundary:

1. Initial: left = 0, right = 5
   Compute mid = (0 + 5) // 2 = 2 → nums[2] = 7
   Since 7 < 8, update left = mid + 1 = 3.
2. Next: left = 3, right = 5
   Compute mid = (3 + 5) // 2 = 4 → nums[4] = 8
   Since 8 is equal to target, move right = mid - 1 = 3 to search further left.
3. Next: left = 3, right = 3
   Compute mid = (3 + 3) // 2 = 3 → nums[3] = 8
   Since 8 is equal to target, update right = mid - 1 = 2.
4. Termination: left = 3, right = 2
   The left boundary is at index 3.

Finding the Right Boundary:

1. Initial: left = 0, right = 5
   Compute mid = (0 + 5) // 2 = 2 → nums[2] = 7
   Since 7 < 8, update left = mid + 1 = 3.
2. Next: left = 3, right = 5
   Compute mid = (3 + 5) // 2 = 4 → nums[4] = 8
   Since 8 equals target, update left = mid + 1 = 5 to search further right.
3. Next: left = 5, right = 5
   Compute mid = (5 + 5) // 2 = 5 → nums[5] = 10
   Since 10 > 8, update right = mid - 1 = 4.
4. Termination: left = 5, right = 4
   The right boundary is at index 4.

Final result is [3, 4].

Code Implementation

Python Implementation