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

描述

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

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

进阶:

你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗?

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

链接

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>
上一篇:34-redis的主从复制


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