What is the best strategy to find the first and last positions of a target in a sorted array?

Use two separate binary searches, one biased left for the first occurrence and one biased right for the last occurrence, ensuring O(log n) efficiency.

How do I handle cases where the target is not present?

After computing the left and right boundaries, validate that nums[left] and nums[right] match the target; otherwise return [-1,-1].

Can this approach work for arrays with duplicates?

Yes, separate left-biased and right-biased binary searches correctly identify the extreme indices even when multiple duplicates exist.

What if the array is empty?

Immediately return [-1,-1] since the binary search will find no valid indices, preventing errors.

Does this problem pattern always require O(log n) solutions?

Yes, the pattern 'binary search over the valid answer space' ensures logarithmic performance, which is necessary for interview expectations.

#34

Medium

auto_awesome二分·搜索·答案·空间

LeetCode 题解工作台

在排序数组中查找元素的第一个和最后一个位置

给你一个按照非递减顺序排列的整数数组 nums ，和一个目标值 target 。请你找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值 target ，返回 [-1, -1] 。你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。示例 1：输入： nums = …

数组二分查找

题目描述

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

示例 1：

输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]

示例 2：

输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]

示例 3：

输入：nums = [], target = 0
输出：[-1,-1]

提示：

0 <= nums.length <= 10⁵
-10⁹ <= nums[i] <= 10⁹
nums 是一个非递减数组
-10⁹ <= target <= 10⁹

lightbulb

解题思路

方法一：二分查找

我们可以进行两次二分查找，分别查找出左边界和右边界。

时间复杂度 $O(\log n)$ ，其中 $n$ 是数组 $\textit{nums}$ 的长度。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        l = bisect_left(nums, target)
        r = bisect_left(nums, target + 1)
        return [-1, -1] if l == r else [l, r - 1]

speed

复杂度分析

指标	值
时间	complexity is O(log n) because each boundary search halves the search space. Space complexity is O(1) since no extra structures are used; only pointers and indices are maintained.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Check if the candidate identifies both leftmost and rightmost positions using separate searches.
question_mark
Listen for correct pointer movement logic to handle duplicates without scanning the entire array.
question_mark
Expect clarification on edge cases, such as empty arrays or targets at array boundaries.

warning

常见陷阱

外企场景

error
Using a single binary search and assuming the first match is the left boundary.
error
Incorrect pointer updates that skip valid duplicates, causing wrong last position.
error
Neglecting validation after search, which can return indices when target is absent.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Find the count of target occurrences using the same binary search boundaries approach.
arrow_right_alt
Return all ranges of multiple target values efficiently in one pass.
arrow_right_alt
Handle rotated sorted arrays while still identifying first and last positions with modified binary search.

help

常见问题

外企场景

继续练习

#33 搜索旋转排序数组 #35 搜索插入位置 #4 寻找两个正序数组的中位数