描述
给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
进阶：
你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗？
链接
34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode） (leetcode-cn.com)
解法一：标准二分法
1 class Solution {
2 public int[] searchRange(int[] nums, int target) {
3
4 // 寻找目标值在数组中的开始位置
5 int firstIdx = findBeginPostion(nums,target);
6
7 // 寻找目标值在数组中的结束位置
8 int lastIdx = findEndPostion(nums,target);
9
10 // 返回寻找的结果
11 return new int[]{firstIdx,lastIdx};
12
13 }
14
15 // 寻找目标值在数组中的开始位置
16 private int findBeginPostion(int[] nums , int target){
17
18 // left 指向当前区间的最左边位置，所以初始化为 0
19 int left = 0;
20
21 // right 指向当前区间的最右边位置，所以初始化为 nums.length - 1
22 int right = nums.length - 1;
23
24 // 循环进行二分查找，直到左端点位置超过了右端点
25 // 或者在循环过程中找到了起始位置
26 while(left <= right){
27
28 // 计算当前区间的中间位置，向下取整
29 int mid = (left + right) / 2;
30
31 // 如果中间位置的元素值等于目标值 target
32 if(nums[mid] == target){
33
34 // 并且中间位置 mid 的左边没有元素，即中间位置 mid 为当前区间的起始位置
35 // 或者中间位置 mid 的前一个元素小于目标值 target
36 // 说明 mid 指向了 target 的起始位置
37 if(mid == 0 || nums[mid - 1] < target){
38 // mid 指向了 target 的起始位置，返回这个结果
39 return mid;
40 }
41
42 // 否则，说明 mid 的左边依然有元素值等于 target
43 // 那么 mid 就不是 target 的起始位置，需要在 mid 的左边进行查找
44 // 所以缩小范围为 left 到 mid - 1
45 // 当前区间的左侧为 left，右侧 right = mid - 1
46 right = mid - 1;
47
48 // 如果中间位置的元素值大于目标值 target
49 // 说明需要在 mid 的左边进行查找
50 }else if( nums[mid] > target){
51
52 // 所以缩小范围为 left 到 mid - 1
53 // 当前区间的左侧为 left，右侧 right = mid - 1
54 right = mid - 1;
55
56 // 如果中间位置的元素值小于目标值 target
57 // 说明需要在 mid 的右边进行查找
58 }else{
59
60 // 所以缩小范围为 mid + 1 到 right
61 // 当前区间的左侧为 left = mid + 1，右侧 right
62 left = mid + 1;
63
64 }
65 }
66
67 // 如果循环结束后还没有返回，说明找不到目标值 target，返回 -1
68 return - 1;
69 }
70
71 // 寻找目标值在数组中的结束位置
72 private int findEndPostion(int[] nums , int target){
73
74 // left 指向当前区间的最左边位置，所以初始化为 0
75 int left = 0;
76
77 // right 指向当前区间的最右边位置，所以初始化为 nums.length - 1
78 int right = nums.length - 1;
79
80 // 循环进行二分查找，直到左端点位置超过了右端点
81 // 或者在循环过程中找到了结束位置
82 while(left <= right){
83
84 // 计算当前区间的中间位置，向下取整
85 int mid = (left + right) / 2;
86
87 // 如果中间位置的元素值等于目标值 target
88 if(nums[mid] == target){
89 // 并且中间位置 mid 的右边没有元素，即中间位置 mid 为当前区间的结束位置
90 // 或者中间位置 mid 的后一个元素大于目标值 target
91 // 说明 mid 指向了 target 的结束位置
92 if(mid == nums.length - 1 || nums[mid + 1] > target){
93 // mid 指向了 target 的结束位置，返回这个结果
94 return mid;
95 }
96
97 // 否则，说明 mid 的右边依然有元素值等于 target
98 // 那么 mid 就不是 target 的结束位置，需要在 mid 的右边进行查找
99 // 所以缩小范围为 mid + 1 到 right
100 // 当前区间的左侧为 left = mid + 1 ，右侧为 right
101 left = mid + 1;
102
103 // 如果中间位置的元素值大于目标值 target
104 // 说明需要在 mid 的左边进行查找
105 }else if( nums[mid] > target){
106
107 // 所以缩小范围为 left 到 mid - 1
108 // 当前区间的左侧为 left，右侧 right = mid - 1
109 right = mid - 1;
110
111 // 如果中间位置的元素值小于目标值 target
112 // 说明需要在 mid 的右边进行查找
113 }else{
114
115 // 所以缩小范围为 mid + 1 到 right
116 // 当前区间的左侧为 left = mid + 1，右侧 right
117 left = mid + 1;
118
119 }
120 }
121
122 // 如果循环结束后还没有返回，说明找不到目标值 target，返回 -1
123 return - 1;
124 }
125
126 }
解法二：二分法，尽量向左压缩
1 public class Solution {
2 public int[] searchRange(int[] nums, int target) {
3 int len = nums.length;
4 if (len == 0) {
5 return new int[]{-1, -1};
6 }
7
8 int firstPosition = findFirstPosition(nums, target);
9 if (firstPosition == -1) {
10 return new int[]{-1, -1};
11 }
12
13 int lastPosition = findLastPosition(nums, target);
14 return new int[]{firstPosition, lastPosition};
15 }
16
17 private int findFirstPosition(int[] nums, int target) {
18 int left = 0;
19 int right = nums.length - 1;
20 while (left < right) {
21 int mid = left + (right - left) / 2;
22 // 小于一定不是解
23 if (nums[mid] < target) {
24 // 下一轮搜索区间是 [mid + 1..right]
25 left = mid + 1;
26 } else {
27 // nums[mid] > target，下一轮搜索区间是 [left..mid]
28 right = mid;
29 }
30 }
31
32 if (nums[left] == target) {
33 return left;
34 }
35 return -1;
36 }
37
38 private int findLastPosition(int[] nums, int target) {
39 int left = 0;
40 int right = nums.length - 1;
41 while (left < right) {
42 int mid = left + (right - left + 1) / 2;
43 if (nums[mid] > target) {
44 // 下一轮搜索区间是 [left..mid - 1]
45 right = mid - 1;
46 } else {
47 // 下一轮搜索区间是 [mid..right]
48 left = mid;
49 }
50 }
51 return left;
52 }
53 }
题解链接
算法训练营第一期 | 在排序数组中查找元素的第一个和最后一个位置_AlgoMooc算法慕课网
<iframe id="videoCont" src="//div.show/videos" style="border: none; visibility: hidden"></iframe>