目錄

問題描述

代碼解決以及思想?

知識(shí)點(diǎn)?

問題描述

代碼解決以及思想?

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

        while (left <= right) {            // 當(dāng)左邊界小于或等于右邊界時(shí)，執(zhí)行循環(huán)
            int middle = left + (right - left) / 2;  // 計(jì)算中間位置，避免整數(shù)溢出

            if (nums[middle] == target) {   // 如果中間元素等于目標(biāo)
                int start = middle;         // 初始化起始和結(jié)束索引為中間索引
                int end = middle;

                // 向左搜索邊界
                while (start > 0 && nums[start - 1] == target) {
                    start--;  // 向左移動(dòng)起始索引，直到不再與目標(biāo)相等
                }

                // 向右搜索邊界
                while (end < (nums.size() - 1) && nums[end + 1] == target) {
                    end++;    // 向右移動(dòng)結(jié)束索引，直到不再與目標(biāo)相等
                }
                return {start, end};  // 返回搜索到的左右邊界
            }
            else if (nums[middle] > target) {
                right = middle - 1;        // 目標(biāo)在左半部分，更新右邊界
            }
            else {
                left = middle + 1;         // 目標(biāo)在右半部分，更新左邊界
            }
        }

        return {-1, -1};  // 如果未找到目標(biāo)元素，返回{-1, -1}表示未找到
    }
};

1. 初始化左邊界 left 為數(shù)組的起始位置（0），右邊界 right 為數(shù)組的結(jié)束位置（nums.size() - 1）。

2. 進(jìn)入一個(gè)循環(huán)，只要左邊界 left 不大于右邊界 right，就執(zhí)行以下操作：

   a. 計(jì)算中間位置 middle，這是為了進(jìn)行二分查找，以避免整數(shù)溢出。

   b. 如果 nums[middle] 等于目標(biāo)元素 target，則表示找到了目標(biāo)元素，然后開始搜索其范圍。

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

   • 向左搜索邊界 start，通過不斷將 start 減小直到不再與目標(biāo)元素相等。
   • 向右搜索邊界 end，通過不斷將 end 增加直到不再與目標(biāo)元素相等。

   d. 返回搜索到的左右邊界，它們代表了目標(biāo)元素在數(shù)組中的范圍。

3. 如果在循環(huán)中找到目標(biāo)元素，則會(huì)在適當(dāng)?shù)臅r(shí)候返回搜索到的范圍。

4. 如果未找到目標(biāo)元素，循環(huán)結(jié)束后，返回 {-1, -1}，表示未找到目標(biāo)元素。

知識(shí)點(diǎn)?

? ? ? ? 進(jìn)行二分查找以找到目標(biāo)元素，然后在找到目標(biāo)元素后，繼續(xù)向左和向右搜索以確定它的范圍。對(duì)于二分查找的內(nèi)容可以看看下面的鏈接：

82.二分查找-CSDN博客

寫在最后：以上就是本篇文章的內(nèi)容了，感謝你的閱讀。如果感到有所收獲的話可以給博主點(diǎn)一個(gè)贊哦。如果文章內(nèi)容有遺漏或者錯(cuò)誤的地方歡迎私信博主或者在評(píng)論區(qū)指出~文章來源地址http://www.zghlxwxcb.cn/news/detail-736179.html

到了這里，關(guān)于84.在排序數(shù)組中查找元素的第一個(gè)和最后一個(gè)位置（力扣）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！