（LeetCodeHot100）34. 在排序数组中查找元素的第一个和最后一个位置——find-first-and-last-position-of-element-in-sorted-array

zhangzhang2025-12-062025-12-07

34. 在排序数组中查找元素的第一个和最后一个位置——find-first-and-last-position-of-element-in-sorted-array

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

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

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

0 <= nums.length <= 105
-109 <= nums[i] <= 109
nums 是一个非递减数组
-109 <= target <= 109

我的正确答案：

还是有点巧妙的，先找到一个target，再左右两边试探一下

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int n = nums.length;
        if (n == 0) {
            return new int[] {-1, -1};
        }
        if (n == 1) {
            return target == nums[0] ? new int[] {0, 0} : new int[] {-1, -1};
        }
        int l = 0, r = n - 1;
        while (l <= r) {
            int mid = (l + r) / 2;
            int[] ans = new int[2]; // 定义结果数组
            if (nums[mid] == target) {
                int flagL = mid - 1, flagR = mid + 1;
                // 依次往左右两边看是不是有一样的
                while (flagL >= 0 && nums[flagL] == target) {
                    flagL--;
                }
                ans[0] = flagL + 1;
                while (flagR < n && nums[flagR] == target) {
                    flagR++;
                }
                ans[1] = flagR - 1;
                return ans;
            }
            // 后面的跟二分查找一样的
            if (nums[mid] > target) {
                r = mid - 1;
            }
            if (nums[mid] < target) {
                l = mid + 1;
            }
        }
        return new int[] {-1, -1};
    }
}

官方解答：

方法：二分查找

直观的思路肯定是从前往后遍历一遍。用两个变量记录第一次和最后一次遇见 target 的下标，但这个方法的时间复杂度为 O(n)，没有利用到数组升序排列的条件。

由于数组已经排序，因此整个数组是单调递增的，我们可以利用二分法来加速查找的过程。

考虑 target 开始和结束位置，其实我们要找的就是数组中「第一个等于 target 的位置」（记为 leftIdx*）和「第一个大于 *target 的位置减一」（记为 rightIdx）。

二分查找中，寻找 leftIdx 即为在数组中寻找第一个大于等于 target 的下标，寻找 rightIdx 即为在数组中寻找第一个大于 target 的下标，然后将下标减一。两者的判断条件不同，为了代码的复用，我们定义 binarySearch(nums, target, lower) 表示在 nums 数组中二分查找 target 的位置，如果 lower 为 true，则查找第一个大于等于 target 的下标，否则查找第一个大于 target 的下标。

最后，因为 target 可能不存在数组中，因此我们需要重新校验我们得到的两个下标 leftIdx 和 rightIdx，看是否符合条件，如果符合条件就返回 [leftIdx,rightIdx]，不符合就返回 [−1,−1]。

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int leftIdx = binarySearch(nums, target, true);
        int rightIdx = binarySearch(nums, target, false) - 1;
        if (leftIdx <= rightIdx && rightIdx < nums.length && nums[leftIdx] == target && nums[rightIdx] == target) {
            return new int[]{leftIdx, rightIdx};
        } 
        return new int[]{-1, -1};
    }

    public int binarySearch(int[] nums, int target, boolean lower) {
        int left = 0, right = nums.length - 1, ans = nums.length;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] > target || (lower && nums[mid] >= target)) {
                right = mid - 1;
                ans = mid;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }
}