顧得泉：個(gè)人主頁(yè)

個(gè)人專欄：《Linux操作系統(tǒng)》??《C/C++》??《LeedCode刷題》

鍵盤(pán)敲爛，年薪百萬(wàn)！

一、二分查找

題目鏈接：二分查找

題目描述

???????給定一個(gè)?n?個(gè)元素有序的（升序）整型數(shù)組?nums?和一個(gè)目標(biāo)值?target??，寫(xiě)一個(gè)函數(shù)搜索?nums?中的?target，如果目標(biāo)值存在返回下標(biāo)，否則返回?-1。
示例 1:

輸入: nums = [-1,0,3,5,9,12], target = 9
輸出: 4
解釋: 9 出現(xiàn)在 nums 中并且下標(biāo)為 4

示例?2:

輸入: nums = [-1,0,3,5,9,12], target = 2
輸出: -1
解釋: 2 不存在 nums 中因此返回 -1

提示：

1. 你可以假設(shè)?nums?中的所有元素是不重復(fù)的。
2. n?將在?[1, 10000]之間。
3. nums?的每個(gè)元素都將在?[-9999, 9999]之間。

解法

a.定義left，right指針，分別指向數(shù)組的左右區(qū)間。

b.找到待查找區(qū)間的中間點(diǎn)mid，找到之后分三種情況討論:

???????i. arr[mid] == target說(shuō)明正好找到，返回mid的值;

???????ii. arr[mid] > target說(shuō)明[mid，right]這段區(qū)間都是大于target的，因此舍去右邊區(qū)間，在左邊[left， mid -1]的區(qū)間繼續(xù)查找，即讓right = mid -1，然后重復(fù)2過(guò)程;

???????iii. arr[mid] < target說(shuō)明[left，mid]這段區(qū)間的值都是小于target的，因此舍去左邊區(qū)間，在右邊[mid + 1，right]區(qū)間繼續(xù)查找，即讓left = mid +1，然后重復(fù)2過(guò)程;

c. 當(dāng)left與right錯(cuò)開(kāi)時(shí)，說(shuō)明整個(gè)區(qū)間都沒(méi)有這個(gè)數(shù)，返回-1

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

int search(int* nums, int numsSize, int target) 
{
    int left = 0, right = numsSize - 1;
    while (left <= right)
    {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) 
            return mid;
        else if (nums[mid] > target)
             right = mid - 1;
        else 
            left = mid + 1;
    }
    return -1;
}

二、在排序數(shù)組中查找元素的第一個(gè)和最后一個(gè)位置

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

題目描述

???????給你一個(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

解法

算法思路:

???????用的還是二分思想，就是根據(jù)數(shù)據(jù)的性質(zhì)，在某種判斷條件下將區(qū)間一分為二，然后舍去其中一個(gè)區(qū)間，然后再另一個(gè)區(qū)間內(nèi)查找

???????方便敘述，用×表示該元素resLeft表示左邊界，resRight表示右邊界。

尋找左邊界思路:

?尋找左邊界:

???????我們注意到以左邊界劃分的兩個(gè)區(qū)間的特點(diǎn):

???????·左邊區(qū)間[left, resLeft - 1]都是小于×的;

???????·右邊區(qū)間(包括左邊界)[resLeft，right]都是大于等于x的;因此，關(guān)于mid的落點(diǎn)，我們可以分為下面兩種情況:

???????當(dāng)我們的mid落在[left，resLeft - 1]區(qū)間的時(shí)候，也就是arr[mid]<target。說(shuō)明[left， mid]都是可以舍去的，此時(shí)更新left到mid + 1的位置,繼續(xù)在[mid + 1, right]上尋找左邊界;

???????當(dāng)mid落在[resLeft，right]的區(qū)間的時(shí)候，也就是arr[mid] >= targeto說(shuō)明[mid + 1，right](因?yàn)閙id可能是最終結(jié)果，不能舍去）是可以舍去的，此時(shí)更新right到mid的位置，繼續(xù)在[left，mid]上尋找左邊界;

???????由此，就可以通過(guò)二分，來(lái)快速尋找左邊界;

注意:

這里找中間元素需要向下取整。因?yàn)楹罄m(xù)移動(dòng)左右指針的時(shí)候:

???????·左指針:left = mid + 1，是會(huì)向后移動(dòng)的，因此區(qū)間是會(huì)縮小的;

???????·右指針: right = mid ，可能會(huì)原地踏步（比如:如果向上取整的話，如果剩下1,2兩個(gè)元素，left == 1，right == 2，mid == 2。更新區(qū)間之后，left，right，mid 的值沒(méi)有改變，就會(huì)陷入死循環(huán))。

???????因此一定要注意，當(dāng)right = mid的時(shí)候，要向下取整。

尋找右邊界思路:

???????尋右左邊界:

???????用resRight表示右邊界;。我們注意到右邊界的特點(diǎn):

???????左邊區(qū)間 (包括右邊界)[left，resRight]都是小于等于的;右邊區(qū)間[resRight+ 1，right]都是大于)的;

???????因此，關(guān)于mid的落點(diǎn)，我們可以分為下面兩種情況:

???????當(dāng)我們的mid落在[left ， resRight了區(qū)間的時(shí)候，說(shuō)明[left，mid - 1]( mid不可以舍去，因?yàn)橛锌赡苁亲罱K結(jié)果）都是可以舍去的，此時(shí)更新left到mid的位置。

???????當(dāng)mid 落在[resRghet ti, right]的區(qū)間的時(shí)候，說(shuō)明[mid，right]內(nèi)的元素是可以舍去的，此時(shí)更新ight到mid - 1的位置;

???????由此，就可以通過(guò)二分，來(lái)快速尋找右邊界

注意:

???????這里找中間元素需要向上取整。因?yàn)楹罄m(xù)移動(dòng)左右指針的時(shí)候:

???????·左指針: left = mid，可能會(huì)原地踏步(比如:如果向下取整的話，如果剩下1,2兩個(gè)元
素，left == 1， right == 2, mid == 1。更新區(qū)間之后，left，right， mid的值沒(méi)有改變，就會(huì)陷入死循環(huán))。

???????·右指針: right = mid - 1，是會(huì)向前移動(dòng)的，因此區(qū)間是會(huì)縮小的;因此一定要注意，當(dāng)right = mid的時(shí)候，要向下取整。

二分查找算法總結(jié):

???????請(qǐng)大家一定不要覺(jué)得背下模板就能解決所有二分問(wèn)題。二分問(wèn)題最重要的就是要分析題意，然后確定要搜索的區(qū)間，根據(jù)分析問(wèn)題來(lái)寫(xiě)出二分查找算法的代碼。

???????要分析題意，確定搜索區(qū)間，不要死記模板，不要看左閉右開(kāi)什么亂七八糟的題解要分析意，確定搜索區(qū)間，不要死記模板，不要看左閉右開(kāi)什么亂七八糟的題解要分析題意，確定搜索區(qū)間，不要死記模板，不要看左閉右開(kāi)什么亂七八糟的題解重要的事情說(shuō)三遍。

模板記憶技巧:

???????1.關(guān)于什么時(shí)候用三段式，還是二段式中的某一個(gè)，一定不要強(qiáng)行去用，而是通過(guò)具體的問(wèn)題分析情況，根據(jù)查找區(qū)間的變化確定指針的轉(zhuǎn)移過(guò)程，從而選擇一個(gè)模板。

???????2.當(dāng)選擇兩段式的模板時(shí):在求mid的時(shí)候，只有right - 1的情況下，才會(huì)向上取整(也就是+i取中間數(shù))

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

class Solution 
{
public:
    vector<int> searchRange(vector<int>& nums, int target) 
    {
        if(nums.size() == 0) return {-1, -1};      
        int begin = 0;
        int left = 0, right = nums.size() - 1;
        while(left < right)
        {
            int mid = left + (right - left) / 2;
            if(nums[mid] < target) 
                left = mid + 1;
            else right = mid;
        }
        if(nums[left] != target) 
            return {-1, -1};
        else begin = left; 
        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, right};
    }
};

三、搜索插入位置

題目鏈接：搜索插入位置

題目描述

???????給定一個(gè)排序數(shù)組和一個(gè)目標(biāo)值，在數(shù)組中找到目標(biāo)值，并返回其索引。如果目標(biāo)值不存在于數(shù)組中，返回它將會(huì)被按順序插入的位置。

???????請(qǐng)必須使用時(shí)間復(fù)雜度為?O(log n)?的算法。

示例 1:

輸入: nums = [1,3,5,6], target = 5
輸出: 2

示例?2:

輸入: nums = [1,3,5,6], target = 2
輸出: 1

示例 3:

輸入: nums = [1,3,5,6], target = 7
輸出: 4

提示:

• 1 <= nums.length <= 104
• -104 <= nums[i] <= 104
• nums?為?無(wú)重復(fù)元素?的?升序?排列數(shù)組
• -104 <= target <= 104

解法

算法思路:

a.分析插入位置左右兩側(cè)區(qū)間上元素的特點(diǎn):

???????設(shè)插入位置的坐標(biāo)為index，根據(jù)插入位置的特點(diǎn)可以知道:

???????[left，index - 1]內(nèi)的所有元素均是小于target的;[index，right]內(nèi)的所有元素均是大于等于target的。

b.設(shè)left為本輪查詢的左邊界，right為本輪查詢的右邊界。

???????根據(jù)mid位置元素的信息，分析下一輪查詢的區(qū)間:

????????·當(dāng)nums [mid] >= target時(shí)，說(shuō)明mid落在了[index，right]區(qū)間上，mid左邊包括mid本身，可能是最終結(jié)果，所以我們接下來(lái)查找的區(qū)間在[left,mid]上。因此，更新right到mid位置,繼續(xù)查找。

???????·當(dāng)nums [mid] < target時(shí)，說(shuō)明mid落在了[left，inde- 1]區(qū)間上，mid右邊但不包括mid本身，可能是最終結(jié)果，所以我們接下來(lái)查找的區(qū)間在[mid+ 1， right]上。因此，更新left到mid + 1的位置，繼續(xù)查找。

c.直到我們的查找區(qū)間的長(zhǎng)度變?yōu)?，也就是(left == right的時(shí)候，left或者right所在的位置就是我們要找的結(jié)果。

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

class Solution 
{
public:
    int searchInsert(vector<int>& nums, int target) 
    {
        int left = 0, right = nums.size() - 1;
        while(left < right)
        {
            int mid = left + (right - left) / 2;
            if(nums[mid] < target) 
                left = mid + 1;
            else right = mid;
        }
        if(nums[left] < target) 
            return right + 1;
        return right;
    }
};

結(jié)語(yǔ)：今日的刷題分享到這里就結(jié)束了，希望本篇文章的分享會(huì)對(duì)大家的學(xué)習(xí)帶來(lái)些許幫助，如果大家有什么問(wèn)題，歡迎大家在評(píng)論區(qū)留言~~~?文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-766434.html

到了這里，關(guān)于LeedCode刷題---二分查找類問(wèn)題的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！