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].

You must write an algorithm with O(log n) runtime complexity.

Examples

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.

Example 2:

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

Example 3:

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

Constraints

  • 0 <= nums.length <= 10^5
  • -10^9 <= nums[i] <= 10^9
  • nums is a non-decreasing array.
  • -10^9 <= target <= 10^9

Thinking Process

  1. Lower Bound vs Upper Bound: Understanding the difference between lower bound (first position >= target) and upper bound (first position > target) is crucial
  • The search space must shrink monotonically each step.
  • Decide which half still satisfies the predicate, discard the other.
  • Use mid = left + (right - left) / 2 to avoid overflow.
Binary search: shrink [lo … hi] lo mid hi discard half each step → O(log n)

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
Standard binary search O(log n) O(1) Sorted array, left <= right
Lower / upper bound O(log n) O(1) First/last position, insert index
Binary search on rotated array (this problem) O(log n) O(1) Identify sorted half, discard other
Binary search on answer O(n log M) O(1) Monotonic predicate over search space

Solution

class Solution:
    def searchRange(self, nums, target):
        if not nums:
            return [-1, -1]
        
        left = self.lowerBound(nums, target)
        
        if left == len(nums) or nums[left] != target:
            return [-1, -1]
        
        right = self.upperBound(nums, target) - 1
        
        return [left, right]
    
    def lowerBound(self, nums, target):
        left, right = 0, len(nums)
        
        while left < right:
            mid = left + (right - left) // 2
            
            if nums[mid] < target:
                left = mid + 1
            else:
                right = mid
        
        return left
    
    def upperBound(self, nums, target):
        left, right = 0, len(nums)
        
        while left < right:
            mid = left + (right - left) // 2
            
            if nums[mid] <= target:
                left = mid + 1
            else:
                right = mid
        
        return left

Solution Explanation

Approach: Binary search on rotated array (this problem)

Key idea: 1. Lower Bound vs Upper Bound: Understanding the difference between lower bound (first position >= target) and upper bound (first position > target) is crucial

How the code works:

  1. Lower Bound vs Upper Bound: Understanding the difference between lower bound (first position >= target) and upper bound (first position > target) is crucial
    • The search space must shrink monotonically each step.
    • Decide which half still satisfies the predicate, discard the other.
    • Use mid = left + (right - left) / 2 to avoid overflow.

Walkthrough — input nums = [5,7,7,8,8,10], target = 8, expected output [3,4]:

The target value 8 appears at indices 3 and 4.

Common Mistakes

  • Skipping edge cases (empty input, single element, boundaries).
  • Off-by-one errors in loops and index ranges.
  • Forgetting to handle the case when no valid answer exists.

Key Takeaways

  1. Lower Bound vs Upper Bound: Understanding the difference between lower bound (first position >= target) and upper bound (first position > target) is crucial
  2. Binary Search Variants: This problem demonstrates two important binary search variants that are commonly used
  3. Boundary Conditions: Careful handling of edge cases (empty array, target not found) is essential
  4. Range Calculation: Upper bound minus 1 gives the last occurrence when target exists

References

Template Reference