題目

給你一個(gè)按照非遞減順序排列的整數(shù)數(shù)組?nums，和一個(gè)目標(biāo)值?target。請(qǐng)你找出給定目標(biāo)值在數(shù)組中的開(kāi)始位置和結(jié)束位置。

如果數(shù)組中不存在目標(biāo)值?target，返回?[-1, -1]。

你必須設(shè)計(jì)并實(shí)現(xiàn)時(shí)間復(fù)雜度為?O(log n)?的算法解決此問(wèn)題。

示例 1：

輸入：nums = [5,7,7,8,8,10], target = 8
輸出：[3,4]

示例?2：

輸入：nums = [5,7,7,8,8,10], target = 6
輸出：[-1,-1]

示例 3：

輸入：nums = [], target = 0
輸出：[-1,-1]

提示：

• 0 <= nums.length <= 105
• -109?<= nums[i]?<= 109
• nums?是一個(gè)非遞減數(shù)組
• -109?<= target?<= 109

算法原理

二分查找的精髓是二段性，不管數(shù)組是否有序，只要數(shù)組存在二段性（即數(shù)組可以分成兩部分），那就可以使用二分查找

1 利用二分查找左端點(diǎn)

? ?假設(shè)要查找的左端點(diǎn)的值為t，t將整個(gè)數(shù)組分為兩部分：

? ?區(qū)間一內(nèi)的所有元素小于t? ?區(qū)間二內(nèi)的所有元素大于等于t

? ?假設(shè)每一次二分mid下標(biāo)對(duì)應(yīng)的值為x

? ?a 若是x<t? 則left = mid+1

? ?b 若是x>=t 則right = mid? （不能是mid+1，因?yàn)閙id可能就是最終答案，若是right=mid+1，那么即將檢索的區(qū)間內(nèi)沒(méi)有了答案）

2 一些細(xì)節(jié)：

? ?a 循環(huán)條件：left<right

? ? ? 不能是left<=right 其一是因?yàn)楫?dāng)left==right時(shí)已經(jīng)有答案了，其二是會(huì)死循環(huán)

? ? ??

b 找中點(diǎn)操作：

? ?1 mid = left+(right-left)/2? 選擇這個(gè)，當(dāng)區(qū)間元素?cái)?shù)為偶數(shù)時(shí)，選擇左側(cè)的為中點(diǎn)

? ?2 mid = left+(right-left+1)/2? 不選這個(gè) 當(dāng)區(qū)間元素?cái)?shù)為偶數(shù)時(shí)，選擇右側(cè)的為中點(diǎn)

? ?

查找左端點(diǎn)時(shí)，當(dāng)區(qū)間內(nèi)只剩下兩個(gè)元素時(shí)?，選擇1，則mid是前一個(gè)元素，那么無(wú)論是left=mid+1，還是right=mid ，left和right最終都會(huì)相等

而選擇2，mid是后一個(gè)元素，若是執(zhí)行right=mid，那么陷入死循環(huán)

3 利用二分查找右端點(diǎn)?

? ?a 若是x<=t 則left = mid（不能是mid+1，因?yàn)閙id可能是最終結(jié)果）

? ?b 若是x>t 則right = mid-1

c 循環(huán)條件：left<right

? ?求中點(diǎn)：mid = left+(right-left+1)/2? left最終都會(huì)等于right?

? ? ? ? ? ? ? ? ?若是選擇?mid = left+(right-left)/2，當(dāng)執(zhí)行l(wèi)eft=mid時(shí)，陷入死循環(huán)文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-704621.html

代碼實(shí)現(xiàn)：

class Solution 
{
public:
    vector<int> searchRange(vector<int>& nums, int target) 
    {
        if(nums.empty())//處理邊界情況
        {
            return {-1,-1};
        }
        //1 二分找左端點(diǎn)
        int left = 0;
        int right = nums.size()-1;
        while(left<right)
        {
            int mid = left+(right-left)/2;
            if(nums[mid]<target)
            {
                left = mid+1;
            }
            else 
            {
                right = mid;
            }
        }

        int begin = 0;
        if(nums[left]==target)
        {
            begin = left;
        }
        else 
        {
            return {-1,-1};
        }

        //2 二分找右端點(diǎn)
        left = 0;
        right = nums.size()-1;
        while(left<right)
        {
            int mid = left+(right-left+1)/2;
            if(nums[mid]<=target)
            {
                left = mid;
            }
            else 
            {
                right = mid-1;
            }
        }
        return {begin,left};
    }
};

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