詳解C語言中二分查找的運用技巧
前篇文章聊到了二分查找的基礎(chǔ)以及細節(jié)的處理問題，主要介紹了 查找和目標值相等的元素、查找第一個和目標值相等的元素、查找最后一個和目標值相等的元素 三種情況。
這些情況都適用于有序數(shù)組中查找指定元素 這個基本的場景，但實際應(yīng)用中可能不會這么直接，甚至看了題目之后，都不會想到可以用二分查找算法來解決 。
本文就來分析下二分查找在實際中的應(yīng)用，通過分析幾個應(yīng)用二分查找的實例，總結(jié)下能使用二分查找算法的一些共同點，以后大家遇到相關(guān)的實際問題時，能有一個基本的分析方法，不至于一點兒頭緒也沒有 。
基礎(chǔ)的二分查
找先來回顧下基礎(chǔ)的二分查找的基本框架，一般實際場景都是查找和 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;
//找到了目標,繼續(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;
}查找右側(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;
//找到了目標，繼續(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;
}二分查找問題分析
二分查找問題的關(guān)鍵是找到一個單調(diào)關(guān)系，單調(diào)遞增或者單調(diào)遞減。
我們把二分查找的代碼簡化下：
int target; // 要查找的目標值
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)系用一個函數(shù) func 來表示，傳入?yún)?shù)是數(shù)組以及數(shù)組索引，函數(shù)返回數(shù)組指定索引處的元素。
在二分查找的 while 循環(huán)中 target 直接和 func 函數(shù)的返回值進行比較。
聽起來有些抽象，我們直接從 leetcode 上選幾道題來分析下。
實例1: 愛吃香蕉的珂珂
從題目的描述，跟有序數(shù)組完全不搭邊，所以初看這道題，根本想不到用二分查找的方法去分析 。
如果看完題目，沒有任何思路的話，可以縷一縷題目涉及到的條件，看能否分析出一些有用的點 。
- 題意分析
- 珂珂要吃香蕉，面前擺了 N 堆，一堆一堆地吃
- 珂珂 1 小時能吃 K 根，但如果一堆少于 K 根，那也得花一小時
- 如果 1 堆大于 K 根，那么超過 K 的部分也算 1 小時
- 問：只給 H 小時，珂珂要吃多慢(K 多小)，才能充分占用這 H 小時
一般題目的問題是什么，單調(diào)關(guān)系就跟什么有關(guān)，根據(jù)題意可知：珂珂吃香蕉的速度越小，耗時越多。反之，速度越大，耗時越少，這就是題目的 單調(diào)關(guān)系 。
我們要找的是速度, 因為題目限制了珂珂一個小時之內(nèi)只能選擇一堆香蕉吃，因此速度最大值就是這幾堆香蕉中，數(shù)量最多的那一堆, 最小速度毫無疑問是 1 了，最大速度可以通過輪詢數(shù)組獲得 。
int maxspeed = 1;
for(auto &elem : vec)
{
if(elem > maxspeed) maxspeed = elem;
}+又因為珂珂一個小時之內(nèi)只能選擇一堆香蕉吃，因此，每堆香蕉吃完的耗時 = 這堆香蕉的數(shù)量 / 珂珂一小時吃香蕉的數(shù)量。根據(jù)題意，這里的 / 在不能整除的時候，還需要花費 1 小時吃完剩下的，所以吃完一堆香蕉花費的時間，可以表示成 。
hour = piles[i] / speed; if(0 != piles[i] % speed) hour += 1;
香蕉的堆數(shù)以及每堆的數(shù)量是確定的，要在 H 小時內(nèi)吃完，時間是輸入?yún)?shù)，也是確定的了，現(xiàn)在唯一不確定的就是吃香蕉的速度，我們需要做的就是在最小速度 到 最大速度之間找出一個速度，使得剛好能在 H 小時內(nèi)吃完香蕉 。
前面說到吃香蕉的速度和吃完香蕉需要的時間之間是單調(diào)關(guān)系，我們先把單調(diào)關(guān)系的函數(shù)定義出來 。
// 速度為 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 小時內(nèi)吃完所有的香蕉，所以是求速度的左側(cè)邊界 。
好了，分析完之后，寫出代碼:
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 函數(shù)代碼見上文
int hours = eatingHour(piles, m);
if (hours == h)
{
// 求速度的左側(cè)邊界
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：運送包裹
題目要求 船的運載能力, 船的運載能力和運輸需要的天數(shù)成反比，運載能力越大，需要的天數(shù)越少，運載能力越小，需要的天數(shù)越多，也即存在 單調(diào)關(guān)系，下面定義出單調(diào)關(guān)系的函數(shù)。
//船的載重為 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ū)間，另外，題目求的是船的最小運載能力，相當于求運載能力的左側(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é)來說，如果發(fā)現(xiàn)題目中存在單調(diào)關(guān)系，就可以嘗試使用二分查找的思路來解決，分析單調(diào)關(guān)系，寫出單調(diào)函數(shù)，搞清楚二分查找的范圍，確定查找的代碼框架，再進行邊界細化，就能夠?qū)懗鲎罱K代碼。
以上就是詳解C語言中二分查找的運用技巧的詳細內(nèi)容，更多關(guān)于C語言二分查找的資料請關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
C語言利用鏈表實現(xiàn)學(xué)生成績管理系統(tǒng)
這篇文章主要為大家詳細介紹了C語言如何利用鏈表實現(xiàn)學(xué)生成績管理系統(tǒng)，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-11-11
避免產(chǎn)生“野指針”最有效的方法，就是在定義指針的同時完成初始化操作，本文主要介紹了C++11?nullptr初始化空指針，感興趣的可以了解一下2022-01-01
這篇文章主要為大家詳細介紹了C語言實現(xiàn)簡易版掃雷游戲，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-05-05
今天小編就為大家分享一篇關(guān)于C++標準模板類的介紹與使用講解，小編覺得內(nèi)容挺不錯的，現(xiàn)在分享給大家，具有很好的參考價值，需要的朋友一起跟隨小編來看看吧2021-09-09
Python擴展C/C++庫的方法(C轉(zhuǎn)換為Python)
這篇文章主要介紹了Python擴展C/C++庫的方法(C轉(zhuǎn)換為Python),本文給大家介紹的非常詳細，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，需要的朋友可以參考下2020-10-10
這篇文章主要介紹了c++中map容器的使用詳解,C++中map容器提供一個鍵值對容器，map與multimap差別僅僅在于multiple允許一個鍵對應(yīng)多個值,需要的朋友可以參考下2023-08-08
在C程序執(zhí)行過程中，其值不發(fā)生改變的量稱為常量，其值可變的量稱為變量，本文將帶你了解什么是常量和變量，以及使用方法，需要的朋友可以參考下2023-05-05
這篇文章主要給大家介紹的是C++解析一些特殊符號tab、換行符號的一些相關(guān)資料,需要的小伙伴可以參考下面文章的具體內(nèi)容2021-09-09
Boost是為C++語言標準庫提供擴展的一些C++程序庫的總稱。Boost庫是一個可移植、提供源代碼的C++庫，作為標準庫的后備，是C++標準化進程的開發(fā)引擎之一，是為C++語言標準庫提供擴展的一些C++程序庫的總稱2022-11-11
關(guān)于指針，其是C語言的重點，C語言學(xué)的好壞，其實就是指針學(xué)的好壞。其實指針并不復(fù)雜，學(xué)習(xí)指針，要正確的理解指針2020-02-02