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

Welcome to our deep dive on Find First and Last Position of Element in Sorted Array (Leetcode 34). This is the quintessential problem for testing your absolute mastery of Binary Search. It forces you to write two specialized implementations to hunt for borders rather than just an exact match.

Problem Statement

Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value.

If target is not found in the array, return [-1, -1].

Constraint: You must write an algorithm with O(log N) runtime complexity.

Example: nums = [5, 7, 7, 8, 8, 10], target = 8 => Output: [3, 4]

Approach 1: Dual Binary Search O(log N)

We are dealing with a sorted array, and the complexity constraint screams O(log N). This guarantees we need to implement a Binary Search.

The conventional binary search stops executing right when nums[mid] == target. But in this problem, there might be multiple 8s scattered. Finding the middle 8 doesn't tell us where the sequence starts or ends!

To find the absolute first position (Left Bound):

• We execute a standard binary search.
• If we hit nums[mid] == target, we log that index as a potential answer.
• However, we do not stop. We aggressively pinch our right pointer to mid - 1 to force the search into the left half to see if an even earlier occurrence exists!

To find the absolute last position (Right Bound):

• If we hit nums[mid] == target, we log that index.
• We aggressively squeeze our left pointer to mid + 1 to force the search into the right half to map out the final trailing 8.

graph TD
    A["nums = [5, 7, 7, 8, 8, 10] | Target: 8"]
    
    B("Search Left Bound") --> C("Hit index 4 (8). Update ans=4")
    C --> D("Squeeze right to mid-1. Search [5, 7, 7, 8]")
    D --> E("Hit index 3 (8). Update ans=3")
    
    F("Search Right Bound") --> G("Hit index 3 (8). Update ans=3")
    G --> H("Squeeze left to mid+1. Search [8, 10]")
    H --> I("Hit index 4 (8). Update ans=4")
    
    style E fill:#FF9800,stroke:#fff,stroke-width:2px,color:#fff
    style I fill:#2196F3,stroke:#fff,stroke-width:2px,color:#fff

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        left_bound = self.binary_search(nums, target, True)
        right_bound = self.binary_search(nums, target, False)
        return [left_bound, right_bound]
        
    def binary_search(self, nums, target, is_searching_left):
        left, right = 0, len(nums) - 1
        pos = -1
        
        while left <= right:
            mid = (left + right) // 2
            
            if nums[mid] > target:
                right = mid - 1
            elif nums[mid] < target:
                left = mid + 1
            else:
                pos = mid
                if is_searching_left:
                    # Target hit! But aggressively map the left chunk
                    right = mid - 1
                else:
                    # Target hit! But aggressively map the right chunk
                    left = mid + 1
                    
        return pos

Complexity Analysis

Try it yourself!

Try this problem on LeetCode (34)