友情支持

如果您觉得这个笔记对您有所帮助,看在D瓜哥码这么多字的辛苦上,请友情支持一下,D瓜哥感激不尽,😜

支付宝

微信

有些打赏的朋友希望可以加个好友,欢迎关注D 瓜哥的微信公众号,这样就可以通过公众号的回复直接给我发信息。

wx jikerizhi

公众号的微信号是: jikerizhi因为众所周知的原因,有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。

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

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

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

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

示例 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 <= 105

  • -109<= nums[i] <= 109

  • nums 是一个非递减数组

  • -109<= target <= 109

思路分析

可以直接使用二分查找,搜索两次。

  • 一刷

  • 二刷

 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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
/**
 * @author D瓜哥 · https://www.diguage.com
 * @since 2018-09-16 20:50 初次完成,2024-07-01 17:24:23 优化
 */
public int[] searchRange(int[] nums, int target) {
  if (nums == null || nums.length == 0) {
    return new int[]{-1, -1};
  }
  // 搜索左边界
  int left = 0, right = nums.length - 1;
  while (left <= right) {
    int mid = left + (right - left) / 2;
    if (nums[mid] < target) {
      left = mid + 1;
    } else if (target < nums[mid]) {
      right = mid - 1;
    } else if (nums[mid] == target) {
      right = mid - 1; // 注意这里的处理
    }
  }
  if (left == nums.length) {
    return new int[]{-1, -1};
  }
  int i1 = -1;
  if (nums[left] == target) {
    i1 = left;
  } else {
    return new int[]{-1, -1};
  }
  // 搜索右边界
  left = 0;
  right = nums.length - 1;
  while (left <= right) {
    int mid = left + (right - left) / 2;
    if (nums[mid] < target) {
      left = mid + 1;
    } else if (target < nums[mid]) {
      right = mid - 1;
    } else if (nums[mid] == target) {
      left = mid + 1; // 注意这里的处理
    }
  }
  if (left - 1 < 0) {
    return new int[]{-1, -1};
  }
  int i2 = -1;
  if (nums[left - 1] == target) {
    i2 = left - 1;
  } else {
    return new int[]{-1, -1};
  }
  return new int[]{i1, i2};
}
 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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
/**
 * @author D瓜哥 · https://www.diguage.com
 * @since 2025-03-04 21:02:59
 */
public int[] searchRange(int[] nums, int target) {
  int left = binarySearch(nums, target, true);
  if (left == -1) {
    return new int[]{-1, -1};
  }
  int right = binarySearch(nums, target, false);
  return new int[]{left, right};
}

private int binarySearch(int[] nums, int target, boolean isLeft) {
  int left = 0;
  int right = nums.length - 1;
  // 使用 result 变量,省去很多繁琐的判断
  int result = -1;
  while (left <= right) {
    int mid = left + (right - left) / 2;
    if (nums[mid] < target) {
      left = mid + 1;
    } else if (target < nums[mid]) {
      right = mid - 1;
    } else {
      if (isLeft) {
        // 注意:找左边界,要收缩右指针
        right = mid - 1;
      } else {
        // 注意:找右边界,要搜索左指针
        left = mid + 1;
      }
      result = mid;
    }
  }
  return result;
}

// 下面是原始代码,上面是优化后的代码
private int binarySearchLeft(int[] nums, int target) {
  int left = 0;
  int right = nums.length - 1;
  // 使用 result 变量,省去很多繁琐的判断
  int result = -1;
  while (left <= right) {
    int mid = left + (right - left) / 2;
    if (nums[mid] < target) {
      left = mid + 1;
    } else if (target < nums[mid]) {
      right = mid - 1;
    } else {
      // 注意:找左边界,要收缩右指针
      right = mid - 1;
      result = mid;
    }
  }
  return result;
}

private int binarySearchRight(int[] nums, int target) {
  int left = 0;
  int right = nums.length - 1;
  // 使用 result 变量,省去很多繁琐的判断
  int result = -1;
  while (left <= right) {
    int mid = left + (right - left) / 2;
    if (nums[mid] < target) {
      left = mid + 1;
    } else if (target < nums[mid]) {
      right = mid - 1;
    } else {
      // 注意:找右边界,要搜索左指针
      left = mid + 1;
      result = mid;
    }
  }
  return result;
}