力扣34在排序数组中查找元素的第一个和最后一个位置：思路分析+图文详解+代码实现（最靠左索引，最靠右索引）

一时失言乱红尘 2024-04-24 14:37 1阅读 0赞

## 第一部分：题目描述 ##

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

⭐ 难度：中等

![image-20230405000813823][]

## 第二部分：思路分析 ##

需要使用 **最靠左索引** 与 **最靠右索引** 解决该问题。

*  最靠左索引：搜索目标值为 target 且 索引最小的索引位置
 *  最靠右索引：搜索目标值为 target 且 索引最大的索引位置

📝 以 最靠左索引 为例来说明：

*  我们知道普通的二分查找是找到一个 目标值 就停止搜索，返回 中间索引 就可以了。
 *  但这里我们需要查找 索引最小的索引位置，那么即使查找到了一个目标值不能直接返回，应该记录下当前的目标值对应的索引，即中间索引mid。
    
    ![image-20230405002114780][]
 *  同时，查找到了这个目标值，我们应该缩小搜索的右边范围，既查找 当前mid索引 左边的范围。
 *  即 需要设置 `right = mid - 1`。
    
    ![image-20230405002405782][]

同理，最靠右索引也需要记录 每次查找到的索引，同时缩小搜索的左边范围，即设置 `left = mid + 1`。

## 第三部分：代码实现 ##

class Solution {
        
        public int[] searchRange(int[] nums, int target) {
        
    
            // 查找最小索引
            int minIndex = searchMinIndex(nums, target);
    
            // 如果未搜索到说明数组不存在目标值
            if (minIndex == -1) {
        
                return new int[]{
        -1, -1};
            }
    
            // 查找最大索引
            int maxIndex = searchMaxIndex(nums, target);
    
            return new int[]{
        minIndex, maxIndex};
        }
    
        private int searchMinIndex(int[] nums, int target) {
        
            int left = 0;
            int right = nums.length - 1;
            // 记录最小索引
            int minIndex = -1;
    
            int mid;
    
            while (left <= right) {
        
                // 无符号右移 代替 /2 操作，避免 left + right 的超出 int能取的最大值
                mid = (left + right) >>> 1;
                if (target < nums[mid]) {
        
                    // 如果 目标值 小于 中间值
                    right = mid - 1;
                } else if (nums[mid] < target) {
        
                    // 如果 目标值 大于 中间值
                    left = mid + 1;
                } else {
        
                    // 记录当前中间索引为最小索引
                    minIndex = mid;
                    // 缩小右范围，以便能向左查找更小的索引
                    right = mid - 1;
                }
            }
            return minIndex;
        }
    
        private int searchMaxIndex(int[] nums, int target) {
        
            int left = 0;
            int right = nums.length - 1;
            // 记录最大索引
            int maxIndex = -1;
    
            int mid;
    
            while (left <= right) {
        
                // 无符号右移 代替 /2 操作，避免 left + right 的超出 int能取的最大值
                mid = (left + right) >>> 1;
                if (target < nums[mid]) {
        
                    // 如果 目标值 小于 中间值
                    right = mid - 1;
                } else if (nums[mid] < target) {
        
                    // 如果 目标值 大于 中间值
                    left = mid + 1;
                } else {
        
                    // 记录当前中间索引为最大索引
                    maxIndex = mid;
                    // 缩小左范围，以便能向右查找更大的索引
                    left = mid + 1;
                }
            }
    
            return maxIndex;
        }
    }

public int[] searchRange(int[] nums, int target) {
        
    
            // 查找最小索引
            int minIndex = searchMinIndex(nums, target);
    
            // 如果未搜索到说明数组不存在目标值
            if (minIndex == -1) {
        
                return new int[]{
        -1, -1};
            }
    
            // 查找最大索引
            int maxIndex = searchMaxIndex(nums, target);
    
            return new int[]{
        minIndex, maxIndex};
        }
    
        private int searchMinIndex(int[] nums, int target) {
        
            int left = 0;
            int right = nums.length - 1;
            // 记录最小索引
            int minIndex = -1;
    
            int mid;
    
            while (left <= right) {
        
                // 无符号右移 代替 /2 操作，避免 left + right 的超出 int能取的最大值
                mid = (left + right) >>> 1;
                if (target < nums[mid]) {
        
                    // 如果 目标值 小于 中间值
                    right = mid - 1;
                } else if (nums[mid] < target) {
        
                    // 如果 目标值 大于 中间值
                    left = mid + 1;
                } else {
        
                    // 记录当前中间索引为最小索引
                    minIndex = mid;
                    // 缩小右范围，以便能向左查找更小的索引
                    right = mid - 1;
                }
            }
            return minIndex;
        }
    
        private int searchMaxIndex(int[] nums, int target) {
        
            int left = 0;
            int right = nums.length - 1;
            // 记录最大索引
            int maxIndex = -1;
    
            int mid;
    
            while (left <= right) {
        
                // 无符号右移 代替 /2 操作，避免 left + right 的超出 int能取的最大值
                mid = (left + right) >>> 1;
                if (target < nums[mid]) {
        
                    // 如果 目标值 小于 中间值
                    right = mid - 1;
                } else if (nums[mid] < target) {
        
                    // 如果 目标值 大于 中间值
                    left = mid + 1;
                } else {
        
                    // 记录当前中间索引为最大索引
                    maxIndex = mid;
                    // 缩小左范围，以便能向右查找更大的索引
                    left = mid + 1;
                }
            }
    
            return maxIndex;
        }

[34. _ - _LeetCode]: https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/
[image-20230405000813823]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/24/2160d6188a0349f881367ec6204eaadf.png
[image-20230405002114780]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/24/9feb60ee673d47039edd50637dbfbde3.png
[image-20230405002405782]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/24/211c51d9367c4e40aec8601e9e494318.png