84.在排序数组中查找元素的第一个和最后一个位置（力扣）-Toy模板网

这篇具有很好参考价值的文章主要介绍了84.在排序数组中查找元素的第一个和最后一个位置（力扣）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

问题描述

代码解决以及思想

知识点

问题描述

84.在排序数组中查找元素的第一个和最后一个位置（力扣）,刷题,leetcode,算法,职场和发展

代码解决以及思想

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int left = 0;                      // 定义左边界
        int right = nums.size() - 1;       // 定义右边界

        while (left <= right) {            // 当左边界小于或等于右边界时，执行循环
            int middle = left + (right - left) / 2;  // 计算中间位置，避免整数溢出

            if (nums[middle] == target) {   // 如果中间元素等于目标
                int start = middle;         // 初始化起始和结束索引为中间索引
                int end = middle;

                // 向左搜索边界
                while (start > 0 && nums[start - 1] == target) {
                    start--;  // 向左移动起始索引，直到不再与目标相等
                }

                // 向右搜索边界
                while (end < (nums.size() - 1) && nums[end + 1] == target) {
                    end++;    // 向右移动结束索引，直到不再与目标相等
                }
                return {start, end};  // 返回搜索到的左右边界
            }
            else if (nums[middle] > target) {
                right = middle - 1;        // 目标在左半部分，更新右边界
            }
            else {
                left = middle + 1;         // 目标在右半部分，更新左边界
            }
        }

        return {-1, -1};  // 如果未找到目标元素，返回{-1, -1}表示未找到
    }
};

初始化左边界 left 为数组的起始位置（0），右边界 right 为数组的结束位置（nums.size() - 1）。

进入一个循环，只要左边界 left 不大于右边界 right，就执行以下操作：

a. 计算中间位置 middle，这是为了进行二分查找，以避免整数溢出。

b. 如果 nums[middle] 等于目标元素 target，则表示找到了目标元素，然后开始搜索其范围。

c. 初始化 start 和 end 为 middle，然后向左和向右搜索边界：

向左搜索边界 start，通过不断将 start 减小直到不再与目标元素相等。

向右搜索边界 end，通过不断将 end 增加直到不再与目标元素相等。

d. 返回搜索到的左右边界，它们代表了目标元素在数组中的范围。

如果在循环中找到目标元素，则会在适当的时候返回搜索到的范围。

如果未找到目标元素，循环结束后，返回 {-1, -1}，表示未找到目标元素。