快捷導(dǎo)航

C++實(shí)現(xiàn)二分法的一些細(xì)節(jié)(常用場(chǎng)景)

更新時(shí)間：2021年07月08日 08:43:10 作者：ZhiboZhao

二分法算法思想首先確定有根區(qū)間，將區(qū)間二等分，通過(guò)判斷f（x）的符號(hào)，逐步將有根區(qū)間縮小，直至有根區(qū)間足夠小，便可求出滿足精度要求的近似值

二分法是在一個(gè)排好序的序列（數(shù)組，鏈表等）中，不斷收縮區(qū)間來(lái)進(jìn)行目標(biāo)值查找的一種算法，下面我們就來(lái)探究二分法使用的一些細(xì)節(jié)，以及常用的場(chǎng)景：

尋找一個(gè)數(shù)；尋找左側(cè)邊界；尋找右側(cè)邊界。

一、二分法的通用框架

int binarySearch(vector<int>& nums, int target){
    int left=0, right=nums.size();
    while(left < right)
    {
        int mid=(left+right)/2;
        if(nums[mid] == target){
            // 條件一：中間的值與目標(biāo)值相同
        }
        else if(nums[mid] > target){
            // 條件二：中間的值大于目標(biāo)值
        }
        else if(nums[mid] < target){
            // 條件三：中間的值小于目標(biāo)值
        }
    }
    return -1;	
}

首先，我們先來(lái)分析一下右邊界 right 的初始值：

當(dāng) right=nums.size() 時(shí)，初始化的區(qū)間就變成了 \([0, right-1]\)，即 \([0,right)\)；
當(dāng)right=nums.size()-1 時(shí)，初始化的區(qū)間就變成了 \([0, right]\)。

在第一種情況下，當(dāng) nums[mid] > target 時(shí)，需要將區(qū)間向左收縮，即 right=mid。這個(gè)做法的邏輯是：既然 mid 位置處大于 target，而查找區(qū)間又是 “左閉右開”，因此當(dāng) right=mid 時(shí)，新的查找區(qū)間變成了 \([0, mid)\)，這樣才不會(huì)漏掉值。同理，當(dāng) nums[mid] < target 時(shí)，需要將區(qū)間向右收縮，即 left = mid+1，因?yàn)樵?"左閉右開" 的區(qū)間下，新的查找區(qū)間變成 \([mid+1, right)\) 才不會(huì)漏掉值。當(dāng)目標(biāo)值不在序列中時(shí)，需要將 while 的條件寫成 while(left < right) 而不是寫成 while(left<=right)，這樣會(huì)引起數(shù)組越界。

第二種情況的分析類似，這里只給出結(jié)論：

當(dāng) nums[mid] > target 時(shí)，需要將區(qū)間向左收縮，即 right=mid-1；
當(dāng) nums[mid] < target 時(shí)，需要將區(qū)間向右收縮，即 left = mid+1；
當(dāng)目標(biāo)值不在序列中時(shí)，需要將 while 的條件寫成 while(left<=right)

二、二分法查找目標(biāo)值

在序列中查找一個(gè)數(shù)，如果存在則返回?cái)?shù)的索引，如果不存在則返回 -1 。為了方便分析，我們就只用第一種情況進(jìn)行說(shuō)明：

int binarySearch(vector<int>& nums, int target){
    int left=0, right=nums.size();
    while(left < right)
    {
        int mid=(left+right)/2;
        if(nums[mid] == target){
           return mid;	// 查詢到目標(biāo)值，直接返回目標(biāo)值的位置
        }
        else if(nums[mid] > target){
            right = mid; // 中間的值大于目標(biāo)值，向左收縮區(qū)間
        }
        else if(nums[mid] < target){
            left = mid+1;// 中間的值小于目標(biāo)值，向右收縮區(qū)間
        }
    }
    return -1;	// 當(dāng)沒(méi)有找到，直接返回-1
}

三、二分法查找目標(biāo)值的左右邊界

上述代碼只能從序列中查找一個(gè)目標(biāo)值并返回位置，當(dāng)一個(gè)序列中目標(biāo)值不止一個(gè)時(shí)，我們需要找到目標(biāo)值最左邊的位置和最右邊的位置，這時(shí)候二分法需要進(jìn)行改寫：

// 查找目標(biāo)值的左邊界
int binarySearch(vector<int>& nums, int target){
    int left=0, right=nums.size();
    while(left < right)
    {
        int mid=(left+right)/2;
        if(nums[mid] == target){
          right = mid;	// 查詢到目標(biāo)值不進(jìn)行返回，而是收縮區(qū)間繼續(xù)查找
        }
        else if(nums[mid] > target){
            right = mid; // 中間的值大于目標(biāo)值，向左收縮區(qū)間
        }
        else if(nums[mid] < target){
            left = mid+1;// 中間的值小于目標(biāo)值，向右收縮區(qū)間
        }
    }
    return left;	
}

根據(jù)上述代碼，可以發(fā)現(xiàn)如果查找目標(biāo)值的左邊界，在滿足 nums[mid] == target 時(shí)，需要縮小搜索區(qū)間的上界 right，在區(qū)間 \([left, mid]\) 中繼續(xù)搜索，直到搜索完畢 left==right。此時(shí) left=right=左邊界。

查找右邊界的做法與左邊界類似：

// 查找目標(biāo)值的左邊界
int binarySearch(vector<int>& nums, int target){
    int left=0, right=nums.size();
    while(left < right)
    {
        int mid=(left+right)/2;
        if(nums[mid] == target){
          left = mid+1;	// 查詢到目標(biāo)值不進(jìn)行返回，而是收縮區(qū)間繼續(xù)查找
        }
        else if(nums[mid] > target){
            right = mid; // 中間的值大于目標(biāo)值，向左收縮區(qū)間
        }
        else if(nums[mid] < target){
            left = mid+1;// 中間的值小于目標(biāo)值，向右收縮區(qū)間
        }
    }
    return left-1;	
}

注意這里的判斷條件改成了當(dāng) nums[mid] == target 時(shí)，left = mid+1。因?yàn)樗阉鞯膮^(qū)間為 "左閉右開"，所以在尋找左邊界時(shí)可令 right=mid ，在尋找右邊界時(shí)必須另 left=mid+1，不然程序會(huì)一直停在循環(huán)里面而無(wú)法跳出循環(huán)。

到此這篇關(guān)于C++實(shí)現(xiàn)二分法詳解的文章就介紹到這了,更多相關(guān)C++實(shí)現(xiàn)二分法內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: