💬 Discord
Sign In
NeetCode #288LC-34MediumBinary Search
← Back to All Problems

#288 · #34 · Find First and Last Position of Element in Sorted Array(在排序数组中查找元素的第一个和最后一个位置)

📌 Problem Statement & Constraints

Given an array of integers nums sorted in non-decreasing order and a target, return the starting and ending position of the target, or [-1, -1] if it is absent. The algorithm must run in O(log n). Constraints: 0 <= nums.length <= 10^5, -10^9 <= nums[i], target <= 10^9.

💡 Core Algorithmic Approaches

  1. Two binary searches: bisect_left finds the first index with value >= target, and bisect_right finds the first index with value > target.
  2. If the left bound is out of range or does not hold the target, the target is absent.
  3. Otherwise the range is [left, right - 1].
  4. Implementing both bounds by hand is a good exercise; using the built-ins is fine in an interview if you can explain the semantics.

💻 Benchmark Python3 Implementation

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        from bisect import bisect_left, bisect_right
        lo = bisect_left(nums, target)     # first index with value >= target
        if lo == len(nums) or nums[lo] != target:
            return [-1, -1]                # target absent
        hi = bisect_right(nums, target) - 1  # last index with value <= target
        return [lo, hi]


# Hand-written bounds, useful to demonstrate the mechanics
class Solution2:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        def lower(x: int) -> int:
            lo, hi = 0, len(nums)
            while lo < hi:
                mid = (lo + hi) // 2
                if nums[mid] < x:
                    lo = mid + 1
                else:
                    hi = mid
            return lo

        lo = lower(target)
        if lo == len(nums) or nums[lo] != target:
            return [-1, -1]
        return [lo, lower(target + 1) - 1]

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(log n): two binary searches.
💾 Space Complexity
O(1): two indices.

⚠️ Interview Pitfalls & Follow-ups

  • Doing one binary search and then expanding linearly: the expansion is O(n) in the worst case (an array of all equal values), violating the O(log n) requirement.
  • Forgetting the absence check: without it, a missing target would return a bogus range.
  • Using bisect_right for the lower bound: that skips equal values.
  • Off-by-one on the upper bound: bisect_right returns the first index after the target, so subtract one.