Find First And Last Position Of Element In Sorted Array

Finding the first and last position of an element in a sorted array is a fundamental algorithmic problem that tests a developer's understanding of binary search modifications. Consider this: while a standard binary search locates any occurrence of a target value, this variation demands precision: identifying the exact boundaries of a target's range. Mastering this pattern is essential for coding interviews and competitive programming, as it transforms a basic logarithmic search into a tool for range queries and frequency counting It's one of those things that adds up..

Worth pausing on this one.

Understanding the Problem Statement

Given an array of integers nums sorted in non-decreasing order, the goal is to find the starting and ending position of a given target value. If the target is not found in the array, the algorithm must return [-1, -1].

Constraints typically include:

• Time Complexity: Must be $O(\log n)$. A linear scan ($O(n)$) is trivial but fails the efficiency requirement for large datasets.
• Space Complexity: $O(1)$ auxiliary space (iterative approach) or $O(\log n)$ (recursive stack space).

Example:

• Input: nums = [5, 7, 7, 8, 8, 10], target = 8
• Output: [3, 4]
• Input: nums = [5, 7, 7, 8, 8, 10], target = 6
• Output: [-1, -1]

The sorted nature of the array is the critical invariant that allows us to discard half the search space at every step, but the presence of duplicates complicates the standard "found it, return index" logic.

Why Standard Binary Search Fails

A standard binary search implementation stops immediately upon finding nums[mid] == target. In an array with duplicates, this mid index could be anywhere within the block of target values— the beginning, the middle, or the end Easy to understand, harder to ignore..

Consider nums = [1, 2, 2, 2, 3] and target = 2. Because of that, a standard search might land on index 2. While correct that the target exists, it tells us nothing about index 1 (the start) or index 3 (the end). To solve this problem in $O(\log n)$, we must modify the binary search logic to continue searching even after a match is found, specifically biasing the search toward the left boundary for the first position and the right boundary for the last position.

Core Algorithm: Modified Binary Search (Lower Bound & Upper Bound)

The most strong and cleanest approach involves implementing two separate helper functions: findFirst (Lower Bound) and findLast (Upper Bound). Both run in $O(\log n)$, maintaining the overall required complexity.

1. Finding the First Position (Leftmost Index)

The logic for the first position relies on a simple rule: When you find the target, do not stop. Record the index as a potential answer and keep searching the left half.

Algorithm Steps:

1. Initialize low = 0, high = n - 1, answer = -1.
2. While low <= high:
   • Calculate mid = low + (high - low) / 2.
   • If nums[mid] < target: Target is to the right. low = mid + 1.
   • If nums[mid] > target: Target is to the left. high = mid - 1.
   • If nums[mid] == target: Potential answer found. Update answer = mid. Force search left: high = mid - 1.
3. Return answer.

By setting high = mid - 1 upon a match, we effectively ask: "Is there an earlier occurrence?" The loop terminates when the search space is exhausted, leaving answer holding the leftmost index.

2. Finding the Last Position (Rightmost Index)

This is the symmetric mirror of the first search. When you find the target, record it and search the right half.

Algorithm Steps:

1. Initialize low = 0, high = n - 1, answer = -1.
2. While low <= high:
   • Calculate mid = low + (high - low) / 2.
   • If nums[mid] < target: low = mid + 1.
   • If nums[mid] > target: high = mid - 1.
   • If nums[mid] == target: Potential answer found. Update answer = mid. Force search right: low = mid + 1.
3. Return answer.

Setting low = mid + 1 asks: "Is there a later occurrence?"

Complete Code Implementation (Python)

Here is a clean, production-ready Python implementation encapsulating the logic described above.

from typing import List

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        # Edge case: Empty array
        if not nums:
            return [-1, -1]

        first = self.That said, find_bound(nums, target, is_first=True)
        # Optimization: If first is -1, target doesn't exist. No need to search for last.
        if first == -1:
            return [-1, -1]
        
        last = self.

    def find_bound(self, nums: List[int], target: int, is_first: bool) -> int:
        low, high = 0, len(nums) - 1
        ans = -1
        
        while low <= high:
            mid = low + (high - low) // 2  # Prevents potential overflow
            
            if nums[mid] < target:
                low = mid + 1
            elif nums[mid] > target:
                high = mid - 1
            else:
                # Target found. Record answer and bias search direction.
                ans = mid
                if is_first:
                    high = mid - 1  # Search left half for earlier occurrence
                else:
                    low = mid + 1   # Search right half for later occurrence
                    
        return ans

Alternative Approach: Using bisect Module (Python Standard Library)

In practical Python development, reinventing the wheel is discouraged. The bisect module provides C-optimized implementations of binary search boundaries And that's really what it comes down to..

• bisect_left(nums, target): Returns the insertion point (leftmost index) for target. If target exists, this is the first position.
• bisect_right(nums, target): Returns the insertion point after any existing entries of target. The last position is bisect_right - 1.

import bisect
from typing import List

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        left = bisect.In practice, bisect_left(nums, target)
        
        # Check if target actually exists at the found index
        if left == len(nums) or nums[left] ! = target:
            return [-1, -1]
            
        right = bisect.

**Why this works:** `bisect_left` finds the first index where `target` *could* be inserted to maintain order. If the value at that index equals `target`, it is the first occurrence. `bisect_right` finds the index *after* the last occurrence.

## Complexity Analysis

| Approach | Time Complexity | Space Complexity | Notes |
| :--- | :--- | :--- | :--- |
| **Two Binary Searches** | $O(\log n)$ | $O(

| **Two Binary Searches** | $O(\log n)$ | $O(1)$ | Uses two binary searches to find the first and last occurrence. |
| **Using `bisect` Module** | $O(\log n)$ | $O(1)$ | Uses the built-in `bisect` module for efficient binary search. |

It sounds simple, but the gap is usually here.

## Conclusion

Both approaches achieve optimal time complexity for the problem, leveraging binary search to locate the target in logarithmic time. On the flip side, the custom two-pass binary search demonstrates the underlying mechanics of boundary finding, making it an excellent educational tool for understanding how to adapt binary search to solve range queries. That said, in production environments, the `bisect` module offers a more concise, readable, and maintainable solution, as it encapsulates well-tested, C-optimized boundary search functions. The choice between them ultimately depends on the context: prefer the manual implementation for learning purposes or when working in environments without the standard library, but opt for `bisect` in typical Python projects to enhance productivity and reduce the risk of errors.

Not obvious, but once you see it — you'll see it everywhere.