詳解C語言中二分查找的運用技巧
前篇文章聊到了二分查找的基礎以及細節(jié)的處理問題,主要介紹了 查找和目標值相等的元素、查找第一個和目標值相等的元素、查找最后一個和目標值相等的元素 三種情況。
這些情況都適用于有序數組中查找指定元素 這個基本的場景,但實際應用中可能不會這么直接,甚至看了題目之后,都不會想到可以用二分查找算法來解決 。
本文就來分析下二分查找在實際中的應用,通過分析幾個應用二分查找的實例,總結下能使用二分查找算法的一些共同點,以后大家遇到相關的實際問題時,能有一個基本的分析方法,不至于一點兒頭緒也沒有 。
基礎的二分查
找先來回顧下基礎的二分查找的基本框架,一般實際場景都是查找和 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; //找到了目標,繼續(xù)向左查找目標 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; //找到了目標,繼續(xù)向右查找目標 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 循環(huán)中 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 循環(huán)中的 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; }
題目中隱含的幾個信息:
- 船的最小載重需要大于等于傳送帶上最重包裹的重量,因為每次至少要裝載一個包裹
- 船的最大載重等于傳送帶上所有包裹的總重量,也即所有的包裹可以一次全部裝上船
- 船每天只能運送一趟包裹
確定了船的運載范圍后,相當于確定了二分查找的區(qū)間,另外,題目求的是船的最小運載能力,相當于求運載能力的左側邊界。
分析到這里,就可以寫出基本的查找框架了,這里直接給出代碼了。
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; }
小結總結來說,如果發(fā)現題目中存在單調關系,就可以嘗試使用二分查找的思路來解決,分析單調關系,寫出單調函數,搞清楚二分查找的范圍,確定查找的代碼框架,再進行邊界細化,就能夠寫出最終代碼。
以上就是詳解C語言中二分查找的運用技巧的詳細內容,更多關于C語言二分查找的資料請關注腳本之家其它相關文章!