個(gè)人主頁 ： 個(gè)人主頁
個(gè)人專欄 ： 《數(shù)據(jù)結(jié)構(gòu)》 《C語言》《C++》《算法》

前言

本篇文章僅是作為小白的我的一些理解，，如果有錯(cuò)誤的地方，希望大佬們指出。

• 題目鏈接： 34. 在排序數(shù)組中查找元素的第一個(gè)和最后一個(gè)位置
  

一、題目解析

本題數(shù)組元素不唯一，可能存在多個(gè)target，我們就是要找到target區(qū)間中的左端點(diǎn)與右端點(diǎn)。

如果沒有target區(qū)間，則返回{-1, -1}

二、解題思路

1. 暴力查找

直接遍歷數(shù)組，如果可以查找到target則返回第一次與最后一次遇到target的下標(biāo)，如果不能查找到target則返回{-1， -1}。
時(shí)間復(fù)雜度：O(n)

2. 一次二分查找 + 部分遍歷

優(yōu)先使用二分查找target，如果可以查找到，就從該下標(biāo)開始向左向右遍歷數(shù)組，返回最左邊與最右邊的target。如果不能查找到，返回{-1, -1}
時(shí)間復(fù)雜度：O(logn + n)

對(duì)于{3,3,3,3,3,3,3,3} target = 3，時(shí)間復(fù)雜度會(huì)退化為O(n)

3. 兩次二分查找分別查找左右端點(diǎn)

1.查找區(qū)間左端點(diǎn)

我們對(duì)示例1使用 “ 二段性 ” 可以發(fā)現(xiàn)示例一被target分成了兩部分，小于target部分{5, 7, 7}和大于等于target部分{8, 8, 10}。

如果中點(diǎn)mid到小于target的部分，區(qū)間[ left, mid ]這一區(qū)間都小于target，不可能是target區(qū)間的左端點(diǎn)，那么left = mid + 1；
如果中點(diǎn)mid到大于等于target的部分，區(qū)間[ mid, right ]這一區(qū)間都大于等于target， 其中mid有可能是target區(qū)間的左端點(diǎn)，那么right = mid；

細(xì)節(jié)處理：

• 循環(huán)條件：left < right
  如果循環(huán)條件為left <= right就會(huì)死循環(huán)。
  

如上圖4所示，nums[mid] >= target，right = mid。此時(shí)right依然與left指向同一個(gè)元素。

• 求mid的操作
  向下取整：mid = left + (right - left)/2 向上取整：mid = left + (right - left + 1)/2；二者主要區(qū)別在與如果區(qū)間[ left, right]中的元素個(gè)數(shù)是偶數(shù)時(shí)，向下取整取的是中間兩個(gè)數(shù)中左邊的數(shù)，向上取整取的是中間兩個(gè)數(shù)中右邊的數(shù)。
  此時(shí)查找區(qū)間左端點(diǎn)，求mid使用向上取整會(huì)導(dǎo)致死循環(huán)。
  

2. 查找區(qū)間右端點(diǎn)

查找區(qū)間右端點(diǎn)思路與查找區(qū)間左端點(diǎn)類似。
我們使用“二段性”發(fā)現(xiàn)示例一被target分成了兩部分，小于等于target部分{5, 7, 7, 8, 8} 和大于target部分{10}。

如果點(diǎn)mid到小于等于target的部分，區(qū)間[ left, mid ] 這一區(qū)間都小于等于target，其中mid可能就是target區(qū)間的右端點(diǎn)，那么left = mid；
如果點(diǎn)mid到大于target的部分，區(qū)間[ mid, right ]這一區(qū)間都大于target，不可能是target區(qū)間的右端點(diǎn)，那么right= mid - 1；

細(xì)節(jié)處理：

• 循環(huán)條件：left < right， 理由與查找左端點(diǎn)使的循環(huán)條件相同，如果循環(huán)條件為left <= right會(huì)死循環(huán)
  
  如上圖4所示，nums[mid] <= target，left = mid， 此時(shí)left依然與right指向同一個(gè)元素。

• 求mid的操作，這里就要用向上取整的方法 mid = left + (right - left + 1)/2
  此處查找區(qū)間右端點(diǎn)，如果使用向下取整會(huì)導(dǎo)致死循環(huán)
  

三、代碼實(shí)現(xiàn)

兩次二分查找分別查找左右端點(diǎn)

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        vector<int> ret({-1, -1});

        int n = nums.size();
        if(n == 0)
            return ret;

        int left = 0, right = n-1;
        // 查找左端點(diǎn)
        while(left < right)
        {
            int mid = left + (right - left)/2;
            if(nums[mid] < target)
                left = mid+1;
            else
                right = mid;
        }
        if(nums[right] == target)
            ret[0] = right;
        
        // 查找右端點(diǎn)
        left = 0, right = n-1;
        while(left < right)
        {
            int mid = left + (right - left + 1)/2;
            if(nums[mid] > target)
                right = mid - 1;
            else
                left = mid;
        }
        if(nums[right] == target)
            ret[1] = right;

        return ret;
    }
};

總結(jié)

以上就是我對(duì)于在排序數(shù)組中查找元素的第一個(gè)和最后一個(gè)位置的理解。感謝支持！?。?br>文章來源地址http://www.zghlxwxcb.cn/news/detail-719438.html

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