在排序数组中查找元素的第一个和最后一个位置(Java详解)

淩亂°似流年 2024-02-05 15:43 8阅读 0赞

## 一、题目描述 ##

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

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

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

**示例：**

> **输入：nums = \[5,7,7,8,8,10\]，target = 8**
> 
> **输出：\[3, 4\]**

> **输入：nums = \[5,7,7,8,8,10\]，target = 6**
> 
> **输出：\[-1, -1\]**

> **输入：nums = \[ \]，target = 0**
> 
> **输出：\[-1, -1\]**

![8c5708046dc24477b6ce8d3498d98e06.png][]

## **二、题解** ##

**思路分析：**

题目要求我们找到出现target的第一个位置和最后一个位置，首先，我们想到可以通过**暴力枚举**的方法来解决该问题，即遍历数组，并记录target第一次出现和最后一次出现的位置。然而，题目要求我们实现时间复杂度为**O(log n)**的算法，且题目中给出的数组为**非递减**的数组，因此，我们可以考虑使用**二分查找**的方法来解决该问题

由于题目中数据量较小，使用遍历的方法也可以通过该题

**遍历代码：**

class Solution {
        public int[] searchRange(int[] nums, int target) {
            int first = -1;
            int last = -1;
            boolean flg = false;//判断是否是第一个位置
            for (int i = 0; i < nums.length; i++) {
                //第一个位置
                if(nums[i] == target && !flg){
                    first = i;
                    flg = true;
                }
                //最后一个位置
                //注意处理特殊情况，即最后一个元素在最后一个位置时，nums[i+1]越界
               if(nums[i] == target && (i == nums.length - 1 || nums[i+1] != target)){
                    last = i;
                }
            }
            int[] ret = {first,last};
            return ret;
        }
    }

> **如何使用二分查找来解决该问题？**

题目要求我们找到target在数组中第一次出现和最后一次出现的位置，利用数组**非递减**的性质

![afd9e1dad0ef48c9a73285bcc55415a0.png][]

> **首先我们查找元素的第一个位置：**

我们可通过target将数组分为**两部分**：

![aab203c32e724682b9da9d5443317fac.png][]

其中，左边部分为**小于**target的元素，右边部分为**大于等于**target的元素，由于右边区域大于等于target，因此**右边区域最左边的值即为target第一次出现的位置，即右边区域的左端点为所求结果**

![3a59950ee55f45f5a309628ed85ec99e.png][]

我们定义left指向0位置，right指向最后一个元素，mid指向中间位置

![2c9bfd4711774f0f8f186fe66b66e4d7.png][]

若mid指向的元素落在右边区间，此时nums\[mid\]大于等于target，需要更新right的值，由于要找的结果（target第一次出现的位置）在此区间内，即mid所指向的位置可能就是最终结果，因此不能将right更新为mid - 1，而应更新为mid

![b61b22fe7b3040f1a91c5b50b9e7e071.png][]

若mid所指向的元素落在左边区间，此时nums\[mid\]小于target，需要更新 left 的值，由于要找的结果不在此区间内，因此可将left的结果更新为 mid + 1

![fe58c9f8519b4753ac4c14a760a7d558.png][]

>  **当left和right之间元素为偶数个时，此时中间元素有两个，应该选择哪一个作为中间元素？**

由于我们查找的是右边区间内最左边的元素，因此，应该选择**左边的元素作为中间元素**

> **若选择右边元素作为中间元素，能够成功查找到结果吗？**

当选择右边元素作为中间元素时，此时会出现死循环的情况，例如：

![cbc32f8934254b8b92fdcc1b93e69b8a.png][] 上图中，当选择右边元素作为中间元素时，mid指向的元素落在右边区间，此时将right更新为mid，再求mid，此时mid仍为指向刚才位置，即落在右边区间，此时再次更新right为mid，再次求mid... 从而死循环

> **循环条件如何设置？**

由于我们将right更新为mid，因此循环的条件应为**left < right**，若循环条件设置为left <= right，当left = right时，此时找到结果，而结果落在右边区间，此时会更新right的值，而right 更新为mid，即当前位置，从而死循环

![f48a67e53a7c40c78d92bc6676d6f5e8.png][]

分析完以上问题后，我们可以尝试编写查找右边区域最左边元素的代码：

//查找target第一次出现的位置(右边区间的左端点)
    int left = 0,right = nums.length - 1,mid = left + (right - left)/2;
    //循环条件应设置为left < right 
    //不能设置为left <= right，否则会死循环
    while(left < right){
        //当mid所指向的元素落在左边区间时，更新left
        if(nums[mid] < target){
            left = mid + 1;
        }else{//当mid所指向的元素落在右边区间时，此时更新right
            //由于右边区间的元素大于等于target，即结果在该区间内，
            // 因此不能将right更新为mid - 1,而应更新为mid
            right = mid;
        }
        //更新mid，当有两个中间元素时，mid应指向其中左边的元素
        mid = left + (right - left) / 2;
    }

> **此时我们查找target最后一次出现的位置**

与查找第一次出现位置的思路相同，我们首先将数组分为两个部分：

![1892caf2245d4b0f86c280c767830008.png][]

其中，左边区间内元素**小于等于**target，右边区间元素**大于**target

此时，要找的结果即为**左边区间的右端点**

![79e6231d8ba14af39aeaeed8f320f309.png][] 同样的，定义left指向0位置，right指向最后一个元素，mid指向中间位置

![bccf52cc81e841a79b03154c1bdc5e5f.png][]

若mid所指向的元素落在左边区间，此时需要更新left的值，由于要找的结果落在此区间内，即mid所指向的位置可能就是最终结果，因此不能将left更新为mid + 1，而应更新为mid

![3b78332aad5b49c685ebcf595969a428.png][]

若mid所指向的元素落在右边区间，此时需要更新right的值，由于要找的结果不在右边区间，因此可将right的值更新为mid - 1

![7cefd21d199644c0ab69bf3119b5f6fa.png][]

> **当left和right之间元素为偶数个时，此时中间元素有两个，应该选择哪一个作为中间元素？**

由于我们查找的是左边区间内最右边的元素，因此，应该选择右边的元素作为中间元素

即 **mid = left + (right - left + 1) / 2;**

同样的，当选择左边元素作为中间元素时，也会造成死循环

![83929a9f51f1401786a19da6aa0e00c6.png][]

此时left的值一直更新为当前位置，造成死循环

> **循环条件的设置：**

循环条件也同样应该设置为**left < right**，否则会死循环

此时我们尝试编写查找左边区间右端点代码：

//查找区间右端点
    left = mid;
    right = nums.length - 1;
    mid = left + (right - left + 1)/2;
    while(left < right){
        //当mid所指向的值落在右边区域时，更新右端点
        if(nums[mid] > target){
            right = mid - 1;
        }else{//当mid所指向的值落在左边区域时，更新左端点
            //由于左边区间的元素小于等于target，即结果在该区间内，
            //因此不能将left更新为mid + 1,而应更新为mid
            left = mid;
        }
        //更新mid的值，若有两个中间元素时，mid应指向其中右边的元素
        mid = left + (right - left + 1) / 2;
    }

**完整代码：**

class Solution {
        public int[] searchRange(int[] nums, int target) {
            int[] ret = {-1,-1};
             //若数组为空，直接返回ret
            if(nums.length == 0){
                return ret;
            }
            //查找target第一次出现的位置(右边区间的左端点)
            int left = 0,right = nums.length - 1,mid = left + (right - left) / 2;
            //循环条件应设置为left < right
            //不能设置为left <= right，否则会死循环
            while(left < right){
                //当mid所指向的元素落在左边区间时，更新left
                if(nums[mid] < target){
                    left = mid + 1;
                }else{//当mid所指向的元素落在右边区间时，此时更新right
                    //由于右边区间的元素大于等于target，即结果在该区间内，
                    // 因此不能将right更新为mid - 1,而应更新为mid
                    right = mid;
                }
                //更新mid，当有两个中间元素时，mid应指向其中左边的元素
                mid = left + (right - left) / 2;
            }
            //此时left = right = mid,使用哪一个变量进行判断和更新都可以
            //若数组中无值为target的元素，直接返回ret
            if(nums[left] == target){
                ret[0] = left;
            }else{
                return ret;
            }
    
            //查找区间右端点
            left = mid;
            right = nums.length - 1;
            mid = left + (right - left + 1)/2;
            while(left < right) {
                //当mid所指向的值落在右边区域时，更新右端点
                if (nums[mid] > target) {
                    right = mid - 1;
                } else {//当mid所指向的值落在左边区域时，更新左端点
                    //由于左边区间的元素小于等于target，即结果在该区间内，
                    //因此不能将left更新为mid + 1,而应更新为mid
                    left = mid;
                }
                //更新mid的值，若有两个中间元素时，mid应指向其中右边的元素
                mid = left + (right - left + 1) / 2;
            }
            ret[1] = left;
            return ret;
        }
    }

**题目来自：**

[34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）][34. _ - _LeetCode]

[8c5708046dc24477b6ce8d3498d98e06.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/05/ea77d2aab92d402685887098b51d3e4d.png
[afd9e1dad0ef48c9a73285bcc55415a0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/05/07cc606790294849a958f4d9fcb913f8.png
[aab203c32e724682b9da9d5443317fac.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/05/8fee69fd4f62471a8220b35b81261c8a.png
[3a59950ee55f45f5a309628ed85ec99e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/05/ce54fd6afe9f49e8b27362b65d5f7d26.png
[2c9bfd4711774f0f8f186fe66b66e4d7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/05/58eb08b9b48e4296bc267ce82f91a372.png
[b61b22fe7b3040f1a91c5b50b9e7e071.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/05/8f42e27b976947fabaefd1ecabbafcfc.png
[fe58c9f8519b4753ac4c14a760a7d558.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/05/fadf29101529426b93b5998c98e06af3.png
[cbc32f8934254b8b92fdcc1b93e69b8a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/05/8ef40410da564e2ab8a9f0e71cb970b5.png
[f48a67e53a7c40c78d92bc6676d6f5e8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/05/5cb487ce33864444bf8a45dbd0118fb7.png
[1892caf2245d4b0f86c280c767830008.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/05/f2bafb4cdf8d4fa39859af9c1188b1f9.png
[79e6231d8ba14af39aeaeed8f320f309.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/05/c81ad335866340699375c8a6ba857992.png
[bccf52cc81e841a79b03154c1bdc5e5f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/05/29f7d57f19134cfa9ff1c9874cab3b3e.png
[3b78332aad5b49c685ebcf595969a428.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/05/b1d1f4ea363146a0a4609afb177734ae.png
[7cefd21d199644c0ab69bf3119b5f6fa.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/05/2f542ecef41b4b1c9c504549c2e4b0d4.png
[83929a9f51f1401786a19da6aa0e00c6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/05/79098a006ecb4955b743cefc216e6d13.png
[34. _ - _LeetCode]: https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/description/