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

发表于 | 分类于 |
字数统计: 744 字 | 阅读时长 ≈ 3 分钟

题目描述：给定一个按照升序排列的整数数组 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]

二分法

当搜索左边界时：找到 target 时不要立即返回，而是缩小 “搜索区间” 的上界 high，在区间 [low, mid - 1] 中继续搜索，即不断向左收缩，达到锁定左侧边界的目的。
当返回时需要判断 low 越界的情况：若 low >= nums.length 或 nums[low] != target 时，说明没有找到目标值 target 返回 -1；否则，返回 low。

当搜索右边界时：找到 target 时不要立即返回，而是增大 “搜索区间” 的下界 low，在区间 [mid + 1, high] 中继续搜索，即不断向右收缩，达到锁定右侧边界的目的。
当返回时需要判断 high 越界的情况：若 high < 0 或 nums[high] != target 时，说明没有找到目标值 target 返回 -1；否则，返回 high。

因为在寻找左侧边界和寻找右侧边界的两个方法中，有许多的重复代码（只有在找到目标值 target 时的区间范围变化不同），为了进行简化，可以在参数中传入 flag 作为标记：当 flag == true 时，为寻找左侧边界；当 flag == false 时，为寻找右侧边界。

当 nums[mid] == target 时，判断 flag 的值，然后利用 mid 对两种情况下的区间边界进行锁定。

在开始遍历之前，定义 ans = -1 变量来记录每次找到目标值 target 时的下标 mid，最后直接返回 ans 即可（不需要进行判断）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] res = new int[] {-1, -1};
        if (nums.length == 0 || nums == null) return res;

        res[0] = binarySearch(nums, target, true);
        res[1] = binarySearch(nums, target, false);
        return res;
    }

    public int binarySearch(int[] nums, int target, boolean flag) {
        int n = nums.length;
        int i = 0, j = n - 1;
        int ans = -1;
        
        while (i <= j) {
            int mid = i + (j - i) / 2;
            if (nums[mid] > target) {
                j = mid - 1;
            } else if (nums[mid] < target) {
                i = mid + 1;
            } else {
                ans = mid;
                if (flag) j = mid - 1;
                else i = mid + 1;                
            }
        }
        return ans;
    }
}

复杂度分析：

  • 时间复杂度： O(logn) ，其中 n 为数组的长度。二分查找的时间复杂度为 O(logn)，一共会执行两次，因此总时间复杂度为 O(logn)。
  • 空间复杂度：O(1) 。只需要常数空间存放若干变量。

执行结果：通过

  • 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
  • 内存消耗：41.6 MB, 在所有 Java 提交中击败了65.37%的用户