詳解C語言中二分查詢的運用技巧

2022-03-29 13:01:32

基礎的二分查

找先來回顧下基礎的二分查詢的基本框架，一般實際場景都是查詢和 target 相等的最左側的元素或者最右側的元素，程式碼如下：

查詢左側邊界

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;
        //找到了目標,繼續向左查詢目標
        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;
}

查詢右側邊界

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;
        //找到了目標，繼續向右查詢目標
        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;
}

二分查詢問題分析

二分查詢問題的關鍵是找到一個單調關係，單調遞增或者單調遞減。

我們把二分查詢的程式碼簡化下：

int target;             // 要查詢的目標值
vector<int> vec;        // 陣列
int left = 0;           // 陣列起始索引
int right = ilen - 1;   // 陣列結束索引
while (left <= right)   // 查詢 target 位於陣列中的索引
{
   int mid = left + (right - left) / 2;
   if (target == vec[mid]) return mid;
}

上面的二分查詢的單調關係是什麼呢 ?是陣列的索引和索引處元素的值，索引越大，元素的值越大，用虛擬碼錶示形式如下：

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
     {
         ...
     }
  }
}

上述虛擬碼中，我們把單調關係用一個函數 func 來表示，傳入引數是陣列以及陣列索引，函數返回陣列指定索引處的元素。

在二分查詢的 while 迴圈中 target 直接和 func 函數的返回值進行比較。

聽起來有些抽象，我們直接從 leetcode 上選幾道題來分析下。

範例1: 愛吃香蕉的珂珂

從題目的描述，跟有序陣列完全不搭邊，所以初看這道題，根本想不到用二分查詢的方法去分析。

如果看完題目，沒有任何思路的話，可以縷一縷題目涉及到的條件，看能否分析出一些有用的點。

題意分析
珂珂要吃香蕉，面前擺了 N 堆，一堆一堆地吃
珂珂 1 小時能吃 K 根，但如果一堆少於 K 根，那也得花一小時
如果 1 堆大於 K 根，那麼超過 K 的部分也算 1 小時
問：只給 H 小時，珂珂要吃多慢(K 多小)，才能充分佔用這 H 小時

一般題目的問題是什麼，單調關係就跟什麼有關，根據題意可知：珂珂吃香蕉的速度越小，耗時越多。反之，速度越大，耗時越少，這就是題目的單調關係。

我們要找的是速度, 因為題目限制了珂珂一個小時之內只能選擇一堆香蕉吃，因此速度最大值就是這幾堆香蕉中，數量最多的那一堆, 最小速度毫無疑問是 1 了，最大速度可以通過輪詢陣列獲得。

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

又因為珂珂一個小時之內只能選擇一堆香蕉吃，因此，每堆香蕉吃完的耗時 = 這堆香蕉的數量 / 珂珂一小時吃香蕉的數量。根據題意，這裡的 / 在不能整除的時候，還需要花費 1 小時吃完剩下的，所以吃完一堆香蕉花費的時間，可以表示成。

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

香蕉的堆數以及每堆的數量是確定的，要在 H 小時內吃完，時間是輸入引數，也是確定的了，現在唯一不確定的就是吃香蕉的速度，我們需要做的就是在最小速度到最大速度之間找出一個速度，使得剛好能在 H 小時內吃完香蕉。

前面說到吃香蕉的速度和吃完香蕉需要的時間之間是單調關係，我們先把單調關係的函數定義出來。

// 速度為 speed 時，吃完所有堆的食物需要多少小時
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 小時內吃完所有的香蕉，所以是求速度的左側邊界。

好了，分析完之後，寫出程式碼:

int minEatingSpeed(vector<int> &piles, int h)
{
    //1小時最多能吃多少根香蕉
    int maxcount = 1;
    for (auto &iter : piles)
    {
        if (maxcount < iter) maxcount = iter; 
    }
    //時間的校驗
    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 函數程式碼見上文
        int hours = eatingHour(piles, m);
        if (hours == h)
        {
            // 求速度的左側邊界
            r_speed = m - 1;
        }
        else if (hours < h)
        {
            // hours 比 h 小，表示速度過大，邊界需要往左邊移動
            r_speed = m - 1;
        }
        else
        {
            // hours 比 h 大，表示速度國小，邊界需要往右邊移動
            l_speed = m + 1;
        }
    }
    return l_speed;
}

上述程式碼中，我們列出了 while 迴圈中的 if 的所有分支，是為了幫助理解的，大家可自行進行合併。

範例2：運送包裹

題目要求船的運載能力, 船的運載能力和運輸需要的天數成反比，運載能力越大，需要的天數越少，運載能力越小，需要的天數越多，也即存在單調關係，下面定義出單調關係的函數。

//船的載重為 capcity 時,運載 weights 貨物需要多少天
int shipDays(const vector<int> &weights, int capacity)
{
    //船載重校驗
    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];
    }
    //還有剩餘的，需要額外在運送一趟
    if(temp > 0)  ++days;
    return days;
}

題目中隱含的幾個資訊：

船的最小載重需要大於等於傳送帶上最重包裹的重量，因為每次至少要裝載一個包裹
船的最大載重等於傳送帶上所有包裹的總重量，也即所有的包裹可以一次全部裝上船
船每天只能運送一趟包裹

確定了船的運載範圍後，相當於確定了二分查詢的區間，另外，題目求的是船的最小運載能力，相當於求運載能力的左側邊界。

分析到這裡，就可以寫出基本的查詢框架了，這裡直接給出程式碼了。

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;
}

小結總結來說，如果發現題目中存在單調關係，就可以嘗試使用二分查詢的思路來解決，分析單調關係，寫出單調函數，搞清楚二分查詢的範圍，確定查詢的程式碼框架，再進行邊界細化，就能夠寫出最終程式碼。

以上就是詳解C語言中二分查詢的運用技巧的詳細內容，更多關於C語言二分查詢的資料請關注it145.com其它相關文章！