欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

詳解C語(yǔ)言中二分查找的運(yùn)用技巧

 更新時(shí)間:2022年03月29日 11:33:43   作者:楓葉  
本文主要介紹了二分查找在實(shí)際中的應(yīng)用,通過(guò)分析幾個(gè)應(yīng)用二分查找的實(shí)例,總結(jié)下能使用二分查找算法的一些共同點(diǎn),感興趣的可以了解一下

前篇文章聊到了二分查找的基礎(chǔ)以及細(xì)節(jié)的處理問(wèn)題,主要介紹了 查找和目標(biāo)值相等的元素、查找第一個(gè)和目標(biāo)值相等的元素、查找最后一個(gè)和目標(biāo)值相等的元素 三種情況。

這些情況都適用于有序數(shù)組中查找指定元素 這個(gè)基本的場(chǎng)景,但實(shí)際應(yīng)用中可能不會(huì)這么直接,甚至看了題目之后,都不會(huì)想到可以用二分查找算法來(lái)解決 。

本文就來(lái)分析下二分查找在實(shí)際中的應(yīng)用,通過(guò)分析幾個(gè)應(yīng)用二分查找的實(shí)例,總結(jié)下能使用二分查找算法的一些共同點(diǎn),以后大家遇到相關(guān)的實(shí)際問(wèn)題時(shí),能有一個(gè)基本的分析方法,不至于一點(diǎn)兒頭緒也沒(méi)有 。

基礎(chǔ)的二分查

找先來(lái)回顧下基礎(chǔ)的二分查找的基本框架,一般實(shí)際場(chǎng)景都是查找和 target 相等的最左側(cè)的元素或者最右側(cè)的元素,代碼如下:

查找左側(cè)邊界

int binary_search_firstequal(vector<int> &vec, int target)
{
    int ilen = (int)vec.size();
    if(ilen <= 0) return -1;
    int left = 0;
    int right = ilen - 1;
    while (left <= right)
    {
        int mid = left + (right - left) / 2;
        //找到了目標(biāo),繼續(xù)向左查找目標(biāo)
        if (target == vec[mid]) right = mid - 1;
        else if(target < vec[mid]) right = mid -1;
        else left = mid + 1;        
    }
    if(right + 1 < ilen && vec[right + 1] == target) return right+1;
    return -1;
}

查找右側(cè)邊界

int binary_search_lastequal(vector<int> &vec, int target)
{
    int ilen = (int)vec.size();
    if(ilen <= 0) return -1;
    int left = 0;
    int right = ilen - 1;
    while (left <= right)
    {
        int mid = left + (right - left) / 2;
        //找到了目標(biāo),繼續(xù)向右查找目標(biāo)
        if (target == vec[mid]) left = mid + 1;
        else if(target < vec[mid]) right = mid -1;
        else left = mid + 1;        
    }
    if(left - 1 < ilen && vec[left - 1] == target) return left - 1;
    return -1;
}

二分查找問(wèn)題分析

二分查找問(wèn)題的關(guān)鍵是找到一個(gè)單調(diào)關(guān)系,單調(diào)遞增或者單調(diào)遞減。

我們把二分查找的代碼簡(jiǎn)化下:

int target;             // 要查找的目標(biāo)值
vector<int> vec;        // 數(shù)組
int left = 0;           // 數(shù)組起始索引
int right = ilen - 1;   // 數(shù)組結(jié)束索引
while (left <= right)   // 查找 target 位于數(shù)組中的索引
{
   int mid = left + (right - left) / 2;
   if (target == vec[mid]) return mid;
}

上面的二分查找的單調(diào)關(guān)系是什么呢 ?是數(shù)組的索引和索引處元素的值,索引越大,元素的值越大,用偽代碼表示形式如下:

int func(vector<int>&vec,int index)
{
    return vec[index];
}
int search(vector<int>&vec,int target)
{
  while (left <= right)
  {
     int mid = left + (right - left) / 2;
     if (target == func(vec,mid))
     {
         ....
     }
     else if(target > func(vec,mid))
     {
         ...
     }
     else
     {
         ...
     }
  }
}

上述偽代碼中,我們把單調(diào)關(guān)系用一個(gè)函數(shù) func 來(lái)表示,傳入?yún)?shù)是數(shù)組以及數(shù)組索引,函數(shù)返回?cái)?shù)組指定索引處的元素。

在二分查找的 while 循環(huán)中 target 直接和 func 函數(shù)的返回值進(jìn)行比較。

聽(tīng)起來(lái)有些抽象,我們直接從 leetcode 上選幾道題來(lái)分析下。

實(shí)例1: 愛(ài)吃香蕉的珂珂

從題目的描述,跟有序數(shù)組完全不搭邊,所以初看這道題,根本想不到用二分查找的方法去分析 。

如果看完題目,沒(méi)有任何思路的話,可以縷一縷題目涉及到的條件,看能否分析出一些有用的點(diǎn) 。

  • 題意分析
  • 珂珂要吃香蕉,面前擺了 N 堆,一堆一堆地吃
  • 珂珂 1 小時(shí)能吃 K 根,但如果一堆少于 K 根,那也得花一小時(shí)
  • 如果 1 堆大于 K 根,那么超過(guò) K 的部分也算 1 小時(shí)
  • 問(wèn):只給 H 小時(shí),珂珂要吃多慢(K 多小),才能充分占用這 H 小時(shí)

一般題目的問(wèn)題是什么,單調(diào)關(guān)系就跟什么有關(guān),根據(jù)題意可知:珂珂吃香蕉的速度越小,耗時(shí)越多。反之,速度越大,耗時(shí)越少,這就是題目的 單調(diào)關(guān)系 。

我們要找的是速度, 因?yàn)轭}目限制了珂珂一個(gè)小時(shí)之內(nèi)只能選擇一堆香蕉吃,因此速度最大值就是這幾堆香蕉中,數(shù)量最多的那一堆, 最小速度毫無(wú)疑問(wèn)是 1 了,最大速度可以通過(guò)輪詢數(shù)組獲得 。

int maxspeed = 1;
for(auto &elem : vec)
{
    if(elem > maxspeed) maxspeed = elem;
}+

又因?yàn)殓骁嬉粋€(gè)小時(shí)之內(nèi)只能選擇一堆香蕉吃,因此,每堆香蕉吃完的耗時(shí) = 這堆香蕉的數(shù)量 / 珂珂一小時(shí)吃香蕉的數(shù)量。根據(jù)題意,這里的 / 在不能整除的時(shí)候,還需要花費(fèi) 1 小時(shí)吃完剩下的,所以吃完一堆香蕉花費(fèi)的時(shí)間,可以表示成 。

hour = piles[i] / speed;
if(0 != piles[i] % speed) hour += 1;

香蕉的堆數(shù)以及每堆的數(shù)量是確定的,要在 H 小時(shí)內(nèi)吃完,時(shí)間是輸入?yún)?shù),也是確定的了,現(xiàn)在唯一不確定的就是吃香蕉的速度,我們需要做的就是在最小速度 到 最大速度之間找出一個(gè)速度,使得剛好能在 H 小時(shí)內(nèi)吃完香蕉 。

前面說(shuō)到吃香蕉的速度和吃完香蕉需要的時(shí)間之間是單調(diào)關(guān)系,我們先把單調(diào)關(guān)系的函數(shù)定義出來(lái) 。

// 速度為 speed 時(shí),吃完所有堆的食物需要多少小時(shí)
int eatingHour(vector<int>&piles,int speed)
{
    if(speed <= 0) return -1;
    int hour = 0;
    for(auto &iter : piles)
    {
        hour += iter / speed;
        if(0 != iter % speed) hour += 1;
    }
    return hour;
}

題目要求吃完香蕉的最小速度,也就是速度要足夠小,小到剛好在 H 小時(shí)內(nèi)吃完所有的香蕉,所以是求速度的左側(cè)邊界 。

好了,分析完之后,寫出代碼:

int minEatingSpeed(vector<int> &piles, int h)
{
    //1小時(shí)最多能吃多少根香蕉
    int maxcount = 1;
    for (auto &iter : piles)
    {
        if (maxcount < iter) maxcount = iter; 
    }
    //時(shí)間的校驗(yàn)
    if (h < 1 || h < (int)piles.size() )  return -1;
    int l_speed = 1;
    int r_speed = maxcount;
    while (l_speed <= r_speed)
    {
        int m = l_speed + (r_speed - l_speed) / 2;
        // eatingHour 函數(shù)代碼見(jiàn)上文
        int hours = eatingHour(piles, m);
        if (hours == h)
        {
            // 求速度的左側(cè)邊界
            r_speed = m - 1;
        }
        else if (hours < h)
        {
            // hours 比 h 小,表示速度過(guò)大,邊界需要往左邊移動(dòng)
            r_speed = m - 1;
        }
        else
        {
            // hours 比 h 大,表示速度國(guó)小,邊界需要往右邊移動(dòng)
            l_speed = m + 1;
        }
    }
    return l_speed;
}

上述代碼中,我們列出了 while 循環(huán)中的 if 的所有分支,是為了幫助理解的,大家可自行進(jìn)行合并。

實(shí)例2:運(yùn)送包裹

題目要求 船的運(yùn)載能力, 船的運(yùn)載能力和運(yùn)輸需要的天數(shù)成反比,運(yùn)載能力越大,需要的天數(shù)越少,運(yùn)載能力越小,需要的天數(shù)越多,也即存在 單調(diào)關(guān)系,下面定義出單調(diào)關(guān)系的函數(shù)。

//船的載重為 capcity 時(shí),運(yùn)載 weights 貨物需要多少天
int shipDays(const vector<int> &weights, int capacity)
{
    //船載重校驗(yàn)
    if(capacity <= 0) return -1;
    int isize = (int)weights.size();
    int temp = 0;
    int days = 0;
    for(int i = 0; i < isize; ++i)
    {
        if(temp + weights[i] <= capacity)
        {
            temp += weights[i];
            continue;
        }
        ++days;
        temp = weights[i];
    }
    //還有剩余的,需要額外在運(yùn)送一趟
    if(temp > 0)  ++days;
    return days;
}

題目中隱含的幾個(gè)信息:

  • 船的最小載重需要大于等于傳送帶上最重包裹的重量,因?yàn)槊看沃辽僖b載一個(gè)包裹
  • 船的最大載重等于傳送帶上所有包裹的總重量,也即所有的包裹可以一次全部裝上船
  • 船每天只能運(yùn)送一趟包裹

確定了船的運(yùn)載范圍后,相當(dāng)于確定了二分查找的區(qū)間,另外,題目求的是船的最小運(yùn)載能力,相當(dāng)于求運(yùn)載能力的左側(cè)邊界。

分析到這里,就可以寫出基本的查找框架了,這里直接給出代碼了。

int shipWithinDays(vector<int> &weights, int days)
{
    int isize = (int)weights.size();
    if (isize <= 0) return 0;
    //最小載重,需要等于貨物的最大重量
    int mincapacity = 0;
    //最大載重,全部貨物重量的總和
    int maxcapacity = 0;
    for (auto &iter : weights)
    {
        maxcapacity += iter;
        if (iter > mincapacity)
        {
            mincapacity = iter;
        }
    }
    int l = mincapacity;
    int r = maxcapacity;
    while (l < r)
    {
        int m = l + (r - l) / 2;
        int d = shipDays(weights, m);
        if (d == days)
        {
            r = m - 1;
        }
        else if (d < days)
        {
            // d 比 days 小,表示船載重太大,載重邊界需要往左移
            r = m - 1;
        }
        else
        {
            // d 比 days 大,表示船載重太小,載重邊界需要往右移
            l = m + 1;
        }
    }
    return l;
}

小結(jié)總結(jié)來(lái)說(shuō),如果發(fā)現(xiàn)題目中存在單調(diào)關(guān)系,就可以嘗試使用二分查找的思路來(lái)解決,分析單調(diào)關(guān)系,寫出單調(diào)函數(shù),搞清楚二分查找的范圍,確定查找的代碼框架,再進(jìn)行邊界細(xì)化,就能夠?qū)懗鲎罱K代碼。

以上就是詳解C語(yǔ)言中二分查找的運(yùn)用技巧的詳細(xì)內(nèi)容,更多關(guān)于C語(yǔ)言二分查找的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章!

相關(guān)文章

  • C語(yǔ)言利用鏈表實(shí)現(xiàn)學(xué)生成績(jī)管理系統(tǒng)

    C語(yǔ)言利用鏈表實(shí)現(xiàn)學(xué)生成績(jī)管理系統(tǒng)

    這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言如何利用鏈表實(shí)現(xiàn)學(xué)生成績(jī)管理系統(tǒng),文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2022-11-11
  • C++11?nullptr實(shí)現(xiàn)初始化空指針

    C++11?nullptr實(shí)現(xiàn)初始化空指針

    避免產(chǎn)生“野指針”最有效的方法,就是在定義指針的同時(shí)完成初始化操作,本文主要介紹了C++11?nullptr初始化空指針,感興趣的可以了解一下
    2022-01-01
  • C語(yǔ)言實(shí)現(xiàn)簡(jiǎn)易版掃雷游戲

    C語(yǔ)言實(shí)現(xiàn)簡(jiǎn)易版掃雷游戲

    這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言實(shí)現(xiàn)簡(jiǎn)易版掃雷游戲,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2021-05-05
  • C++ 標(biāo)準(zhǔn)模板類詳解

    C++ 標(biāo)準(zhǔn)模板類詳解

    今天小編就為大家分享一篇關(guān)于C++標(biāo)準(zhǔn)模板類的介紹與使用講解,小編覺(jué)得內(nèi)容挺不錯(cuò)的,現(xiàn)在分享給大家,具有很好的參考價(jià)值,需要的朋友一起跟隨小編來(lái)看看吧
    2021-09-09
  • Python擴(kuò)展C/C++庫(kù)的方法(C轉(zhuǎn)換為Python)

    Python擴(kuò)展C/C++庫(kù)的方法(C轉(zhuǎn)換為Python)

    這篇文章主要介紹了Python擴(kuò)展C/C++庫(kù)的方法(C轉(zhuǎn)換為Python),本文給大家介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下
    2020-10-10
  • c++中map容器的使用詳解

    c++中map容器的使用詳解

    這篇文章主要介紹了c++中map容器的使用詳解,C++中map容器提供一個(gè)鍵值對(duì)容器,map與multimap差別僅僅在于multiple允許一個(gè)鍵對(duì)應(yīng)多個(gè)值,需要的朋友可以參考下
    2023-08-08
  • 淺析C語(yǔ)言初階的常量和變量

    淺析C語(yǔ)言初階的常量和變量

    在C程序執(zhí)行過(guò)程中,其值不發(fā)生改變的量稱為常量,其值可變的量稱為變量,本文將帶你了解什么是常量和變量,以及使用方法,需要的朋友可以參考下
    2023-05-05
  • C++解析特殊符號(hào)tab和換行符號(hào)詳情

    C++解析特殊符號(hào)tab和換行符號(hào)詳情

    這篇文章主要給大家介紹的是C++解析一些特殊符號(hào)tab、換行符號(hào)的一些相關(guān)資料,需要的小伙伴可以參考下面文章的具體內(nèi)容
    2021-09-09
  • C++ Boost PropertyTree示例超詳細(xì)講解

    C++ Boost PropertyTree示例超詳細(xì)講解

    Boost是為C++語(yǔ)言標(biāo)準(zhǔn)庫(kù)提供擴(kuò)展的一些C++程序庫(kù)的總稱。Boost庫(kù)是一個(gè)可移植、提供源代碼的C++庫(kù),作為標(biāo)準(zhǔn)庫(kù)的后備,是C++標(biāo)準(zhǔn)化進(jìn)程的開(kāi)發(fā)引擎之一,是為C++語(yǔ)言標(biāo)準(zhǔn)庫(kù)提供擴(kuò)展的一些C++程序庫(kù)的總稱
    2022-11-11
  • 深入理解C語(yǔ)言指針

    深入理解C語(yǔ)言指針

    關(guān)于指針,其是C語(yǔ)言的重點(diǎn),C語(yǔ)言學(xué)的好壞,其實(shí)就是指針學(xué)的好壞。其實(shí)指針并不復(fù)雜,學(xué)習(xí)指針,要正確的理解指針
    2020-02-02

最新評(píng)論