Pseudo-code:

text
function bruteForce(nums, target):
    first = -1
    last = -1
    for i from 0 to length(nums) - 1:
        if nums[i] == target:
            if first == -1:
                first = i
            last = i
    return [first, last]

Time Complexity Analysis: The time complexity is O(n), where n is the number of elements in the array. In the worst case, we must traverse the entire array.

Why it fails: While this solution produces the correct output, it violates the explicit problem constraint requiring O(log n) runtime complexity. In a large dataset (up to $10^5$ elements), an O(n) solution is significantly slower than O(log n), and in an interview context, this solution would be considered suboptimal.

Core Insight for Find First and Last Position of Element in Sorted Array

The standard binary search algorithm returns the index of any occurrence of the target. However, it does not guarantee finding the first or last occurrence when duplicates exist.

To solve LeetCode 34 efficiently, we must recognize that finding the "first" position and the "last" position are two separate sub-problems that can be solved using the same logic with a slight variation.

The Key Invariant: When we find nums[mid] == target, we have found an instance of the target, but we do not stop.

1. To find the First Position: We record the current mid as a potential answer but assume the true first position might lie to the left. Therefore, we narrow the search space to [low, mid - 1].
2. To find the Last Position: We record the current mid as a potential answer but assume the true last position might lie to the right. Therefore, we narrow the search space to [mid + 1, high].

Visual Description: Imagine the array as a series of blocks. The binary search repeatedly cuts the search space in half.

• In the first pass, even if the algorithm lands on the target, it treats the right half as "discardable" to push the search pointer as far left as possible.
• In the second pass, it treats the left half as "discardable" upon finding a match to push the search pointer as far right as possible. The search terminates only when the low and high pointers cross, ensuring the boundary has been identified precisely.

Execution Flow

Let's trace the algorithm with nums = [5, 7, 7, 8, 8, 10] and target = 8.

Pass 1: Find First Position

1. low=0, high=5, mid=2. nums[2] is 7. $7 < 8$, so low becomes 3.
2. low=3, high=5, mid=4. nums[4] is 8.
   • Target found. Store index = 4.
   • We want the first position, so we look left. high becomes 3.
3. low=3, high=3, mid=3. nums[3] is 8.
   • Target found. Store index = 3.
   • We want the first position, so we look left. high becomes 2.
4. low=3, high=2. Loop terminates. First Position = 3.

Pass 2: Find Last Position

1. low=0, high=5, mid=2. nums[2] is 7. $7 < 8$, so low becomes 3.
2. low=3, high=5, mid=4. nums[4] is 8.
   • Target found. Store index = 4.
   • We want the last position, so we look right. low becomes 5.
3. low=5, high=5, mid=5. nums[5] is 10. $10 > 8$, so high becomes 4.
4. low=5, high=4. Loop terminates. Last Position = 4.

Result: [3, 4].

Proof of Correctness

The correctness relies on the monotonicity of the sorted array.

1. Termination: The while (low <= high) loop is guaranteed to terminate because the search space reduces by roughly half in each iteration, eventually causing pointers to cross.
2. Completeness: If the target exists, nums[mid] == target will eventually be true.
3. Boundary Finding: By strictly moving high to mid - 1 after a match (when finding the first), we ensure that we never settle for a non-minimal index. We exhaustively verify that no target exists to the left of the current candidate. The symmetric logic applies to finding the last index.

Reference Implementation

C++ Solution for LeetCode 34

cpp
class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        vector<int> result = {-1, -1};
        result[0] = findBound(nums, target, true);  // Find first
        if (result[0] == -1) return result;         // Target not found
        result[1] = findBound(nums, target, false); // Find last
        return result;
    }

private:
    int findBound(vector<int>& nums, int target, bool isFirst) {
        int left = 0, right = nums.size() - 1;
        int boundIndex = -1;

        while (left <= right) {
            int mid = left + (right - left) / 2;

            if (nums[mid] == target) {
                boundIndex = mid;
                // If finding first, narrow search to left half
                if (isFirst) {
                    right = mid - 1;
                } 
                // If finding last, narrow search to right half
                else {
                    left = mid + 1;
                }
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return boundIndex;
    }
};

Java Solution for LeetCode 34

java
class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] result = new int[]{-1, -1};
        result[0] = findBound(nums, target, true);
        
        // If the target isn't found once, it won't be found twice
        if (result[0] == -1) {
            return result;
        }
        
        result[1] = findBound(nums, target, false);
        return result;
    }

    private int findBound(int[] nums, int target, boolean isFirst) {
        int left = 0;
        int right = nums.length - 1;
        int index = -1;

        while (left <= right) {
            int mid = left + (right - left) / 2;

            if (nums[mid] == target) {
                index = mid;
                if (isFirst) {
                    right = mid - 1; // Continue searching left
                } else {
                    left = mid + 1;  // Continue searching right
                }
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return index;
    }
}

Python Solution for LeetCode 34

python
class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        
        def find_bound(is_first: bool) -> int:
            left, right = 0, len(nums) - 1
            bound_index = -1
            
            while left <= right:
                mid = left + (right - left) // 2
                
                if nums[mid] == target:
                    bound_index = mid
                    if is_first:
                        right = mid - 1  # Narrow search to left
                    else:
                        left = mid + 1   # Narrow search to right
                elif nums[mid] < target:
                    left = mid + 1
                else:
                    right = mid - 1
            
            return bound_index

        start = find_bound(True)
        if start == -1:
            return [-1, -1]
        
        end = find_bound(False)
        return [start, end]

Q: Can I use a linear scan after finding the first match? Mistake: Finding one instance via binary search, then expanding outwards linearly (e.g., while nums[i] == target: i++). Explanation: While this works for small duplicate counts, the problem constraints allow for cases where the array consists entirely of the target value (e.g., $10^5$ copies of '8'). Consequence: Efficiency failure. The worst-case complexity degrades to $O(n)$, violating the strict $O(\log n)$ requirement.