模板：從算法到泛型編程的通用實(shí)現(xiàn))
1. 項(xiàng)目概述從“二分”到“函數(shù)模板”的通用化之旅在編程世界里“二分”是一個(gè)既古老又充滿活力的概念。無(wú)論是剛?cè)腴T的新手在力扣上刷題還是資深工程師在優(yōu)化海量數(shù)據(jù)查詢二分查找Binary Search都是繞不開的基石算法。它的核心思想簡(jiǎn)單而優(yōu)雅在一個(gè)有序的集合中通過不斷與中間元素比較將搜索范圍對(duì)半縮小從而以對(duì)數(shù)級(jí)的時(shí)間復(fù)雜度O(log n)快速定位目標(biāo)。然而當(dāng)我們從解決單一問題邁向構(gòu)建健壯、可復(fù)用的代碼庫(kù)時(shí)一個(gè)原始的二分查找實(shí)現(xiàn)就顯得捉襟見肘了。你可能會(huì)為整型數(shù)組寫一個(gè)版本為浮點(diǎn)數(shù)向量再寫一個(gè)為自定義結(jié)構(gòu)體又得重頭來(lái)過——代碼重復(fù)維護(hù)成本陡增。這正是“函數(shù)模板”大顯身手的地方。將“二分”與“函數(shù)模板”結(jié)合其核心目標(biāo)就是實(shí)現(xiàn)一個(gè)與數(shù)據(jù)類型無(wú)關(guān)的、通用的二分查找算法。它不再僅僅是一個(gè)解決特定問題的代碼片段而是一個(gè)可以被復(fù)用的“工具”。無(wú)論你的數(shù)據(jù)是int、double、std::string還是你自己定義的Student對(duì)象只要這些數(shù)據(jù)能夠被比較即定義了或等操作這個(gè)模板化的二分函數(shù)就能無(wú)縫工作。這背后體現(xiàn)的是泛型編程Generic Programming的思想將算法與數(shù)據(jù)結(jié)構(gòu)分離讓算法獨(dú)立于任何特定的數(shù)據(jù)類型。對(duì)于初學(xué)者理解這個(gè)組合能幫你跨越“會(huì)寫算法”到“會(huì)設(shè)計(jì)通用工具”的鴻溝對(duì)于有經(jīng)驗(yàn)的開發(fā)者一個(gè)精心打磨的二分函數(shù)模板是工具箱里的瑞士軍刀能在各種場(chǎng)景下快速部署提升開發(fā)效率與代碼質(zhì)量。接下來(lái)我們就深入拆解如何構(gòu)建這樣一個(gè)既強(qiáng)大又靈活的二分查找函數(shù)模板。2. 核心思路與設(shè)計(jì)考量2.1 為何需要模板化從具體到抽象的必然假設(shè)我們有一個(gè)最簡(jiǎn)單的整型數(shù)組二分查找int binarySearch_int(int arr[], int size, int target) { int left 0, right size - 1; while (left right) { int mid left (right - left) / 2; // 防止溢出 if (arr[mid] target) return mid; else if (arr[mid] target) left mid 1; else right mid - 1; } return -1; // 未找到 }這個(gè)函數(shù)工作得很好但局限性也顯而易見它只能處理int類型的數(shù)組。如果明天需要處理std::vectordouble你就得復(fù)制一份代碼把所有的int改成double。這種重復(fù)不僅枯燥更危險(xiǎn)的是當(dāng)你發(fā)現(xiàn)原函數(shù)有一個(gè)邊界條件bug時(shí)你需要記住在所有拷貝的版本中進(jìn)行同樣的修改極易出錯(cuò)。函數(shù)模板通過引入一個(gè)“類型參數(shù)”來(lái)解決這個(gè)問題。你可以把類型參數(shù)T想象成一個(gè)占位符編譯器會(huì)在你調(diào)用函數(shù)時(shí)用實(shí)際的類型如int、double來(lái)替換它自動(dòng)為你生成對(duì)應(yīng)類型的函數(shù)版本。這樣你只需維護(hù)一份源代碼。2.2 設(shè)計(jì)決策迭代器與比較函數(shù)的引入一個(gè)工業(yè)級(jí)的二分函數(shù)模板絕不會(huì)僅僅滿足于處理內(nèi)置類型的數(shù)組。它的設(shè)計(jì)需要更普適。這里有兩個(gè)關(guān)鍵的設(shè)計(jì)決策1. 使用迭代器Iterators而非原生指針或容器我們最初的例子使用了C風(fēng)格數(shù)組和指針運(yùn)算。但在現(xiàn)代C中標(biāo)準(zhǔn)庫(kù)容器如vector,list,array和算法都基于迭代器設(shè)計(jì)。迭代器是一種抽象它統(tǒng)一了對(duì)不同數(shù)據(jù)結(jié)構(gòu)連續(xù)內(nèi)存如數(shù)組或非連續(xù)內(nèi)存如鏈表的訪問方式。我們的二分模板如果接受一對(duì)迭代器[first, last)來(lái)表示搜索范圍那么它將能應(yīng)用于所有標(biāo)準(zhǔn)庫(kù)順序容器vector,deque,array,list的部分操作原生數(shù)組甚至用戶自定義的、提供了迭代器的容器 這極大地?cái)U(kuò)展了函數(shù)的適用范圍。[first, last)是一個(gè)左閉右開區(qū)間這是STL的慣例使得表示空范圍first last和計(jì)算元素?cái)?shù)量last - first都非常自然。2. 支持自定義比較函數(shù)Comparator標(biāo)準(zhǔn)的二分查找要求數(shù)據(jù)有序。但“有序”的標(biāo)準(zhǔn)是什么對(duì)于整數(shù)是數(shù)值大小對(duì)于字符串可能是字典序?qū)τ谧远x的Person對(duì)象你可能想按年齡或姓名排序。因此一個(gè)通用的二分函數(shù)必須允許用戶傳入一個(gè)自定義的比較準(zhǔn)則。 通常我們提供一個(gè)默認(rèn)參數(shù)為std::lessT()它使用類型的運(yùn)算符。同時(shí)允許用戶傳入任何可調(diào)用對(duì)象函數(shù)指針、函數(shù)對(duì)象、lambda表達(dá)式來(lái)定義自己的“小于”關(guān)系。這使得模板不僅能查找值還能用于更復(fù)雜的場(chǎng)景比如在單調(diào)函數(shù)上查找滿足某個(gè)條件的第一個(gè)位置二分答案的思想。注意比較函數(shù)必須與排序時(shí)使用的比較規(guī)則一致否則二分查找的前提有序性被破壞結(jié)果將不可預(yù)測(cè)。這是使用自定義比較器時(shí)最容易踩的坑?；谝陨峡剂课覀兡繕?biāo)函數(shù)的原型逐漸清晰templatetypename Iter, typename T, typename Comp bool binary_search(Iter first, Iter last, const T value, Comp comp)。3. 核心細(xì)節(jié)解析與實(shí)現(xiàn)要點(diǎn)3.1 函數(shù)模板的語(yǔ)法骨架首先我們搭建模板的聲明部分。這里需要聲明三個(gè)模板參數(shù)typename Iter迭代器類型代表數(shù)據(jù)序列的訪問方式。typename T要查找的值的類型。注意這個(gè)類型不一定與迭代器解引用后的類型完全相同但必須能與之間接比較通過Comp。typename Comp比較函數(shù)對(duì)象的類型默認(rèn)使用std::lesstypename std::iterator_traitsIter::value_type。這里用到了std::iterator_traits來(lái)安全地獲取迭代器指向的元素類型比直接假設(shè)更魯棒。#include iterator // for iterator_traits #include functional // for less template typename Iter, typename T, typename Comp std::lesstypename std::iterator_traitsIter::value_type bool binary_search_template(Iter first, Iter last, const T value, Comp comp Comp()) { // 實(shí)現(xiàn)細(xì)節(jié)將在下文展開 }3.2 迭代器運(yùn)算與“中間點(diǎn)”的計(jì)算在循環(huán)體內(nèi)我們需要計(jì)算當(dāng)前搜索范圍的中間點(diǎn)。對(duì)于像vector這樣的隨機(jī)訪問迭代器我們可以直接用first (last - first) / 2。但對(duì)于像list這樣的雙向迭代器這種加減法是無(wú)效的。為了寫出真正通用的代碼我們不能直接對(duì)迭代器進(jìn)行加法。正確的通用做法是使用std::distance(first, last)計(jì)算區(qū)間長(zhǎng)度。這個(gè)函數(shù)對(duì)于隨機(jī)訪問迭代器是O(1)對(duì)于其他迭代器是O(n)但在二分查找的上下文中我們通常假設(shè)迭代器至少是前向迭代器且distance只在循環(huán)外或邏輯判斷中使用影響不大。使用std::advance將迭代器移動(dòng)特定的距離。更常見的寫法是先復(fù)制first迭代器然后移動(dòng)它的副本。在實(shí)際的二分查找實(shí)現(xiàn)中我們通常采用一種不直接計(jì)算總長(zhǎng)度的方法它適用于任何前向迭代器雖然對(duì)于非隨機(jī)訪問迭代器效率低但語(yǔ)法正確while (first ! last) { Iter mid first; std::advance(mid, std::distance(first, last) / 2); // ... 比較邏輯 }然而對(duì)于二分查找我們通常期望在隨機(jī)訪問數(shù)據(jù)結(jié)構(gòu)上使用以獲得O(log n)的性能。因此在文檔或接口約定中可以注明“該函數(shù)對(duì)迭代器類別的要求為隨機(jī)訪問迭代器”并在實(shí)現(xiàn)中使用first (last - first) / 2這種高效形式。這是一種在通用性和性能之間的權(quán)衡。為了教學(xué)和通用性我們先展示完全通用的版本但需要明白其潛在的性能影響。3.3 比較邏輯與邊界移動(dòng)這是二分查找的核心邏輯。我們需要用傳入的comp函數(shù)對(duì)象來(lái)比較*mid和value。如果comp(*mid, value)為真意味著*mid value根據(jù)自定義規(guī)則那么目標(biāo)值只可能在后半段移動(dòng)first std::next(mid)。如果comp(value, *mid)為真意味著value *mid那么目標(biāo)值只可能在前半段移動(dòng)last mid。如果兩者都為假根據(jù)邏輯意味著!comp(*mid, value) !comp(value, *mid)這通常等價(jià)于*mid value在嚴(yán)格弱序下此時(shí)我們找到了目標(biāo)。這里有一個(gè)極其重要的細(xì)節(jié)我們不應(yīng)該直接使用*mid value來(lái)判斷相等。因?yàn)橛脩艨赡軅魅肓艘粋€(gè)自定義的比較器它定義的“等價(jià)”不等于operator。在嚴(yán)格弱序中兩個(gè)元素a和b“等價(jià)”的定義是!comp(a, b) !comp(b, a)。我們的查找函數(shù)應(yīng)該遵循這個(gè)定義這樣才能與STL的std::binary_search等算法保持行為一致。3.4 返回值的設(shè)計(jì)基礎(chǔ)的二分查找通常返回找到元素的索引或迭代器。我們的模板示例返回bool表示是否存在。這是一種簡(jiǎn)潔的設(shè)計(jì)。你也可以設(shè)計(jì)為返回迭代器找到時(shí)返回指向該元素的迭代器未找到時(shí)返回last這樣調(diào)用者能獲得更多信息。STL的std::lower_bound就是返回迭代器的典范它返回第一個(gè)不小于value的元素位置可以同時(shí)用于查找和插入。在我們的實(shí)現(xiàn)中為了聚焦于模板本身先采用返回bool的簡(jiǎn)單形式。4. 完整實(shí)現(xiàn)與逐行解析結(jié)合以上所有要點(diǎn)我們給出一個(gè)完整、健壯且?guī)в性敿?xì)注釋的二分查找函數(shù)模板實(shí)現(xiàn)。#include iterator #include functional /** * brief 通用的二分查找函數(shù)模板。 * * tparam Iter 前向迭代器類型至少支持前向遍歷。對(duì)于隨機(jī)訪問迭代器有最佳性能。 * tparam T 要查找的值的類型。 * tparam Comp 比較函數(shù)對(duì)象類型默認(rèn)使用 std::less迭代器值類型。 * param first 搜索范圍的起始迭代器包含。 * param last 搜索范圍的結(jié)束迭代器不包含。 * param value 要查找的目標(biāo)值。 * param comp 用于比較的函數(shù)對(duì)象默認(rèn)為 Comp()。 * return true 如果在范圍 [first, last) 中找到等價(jià)于 value 的元素。 * return false 否則。 * * pre 范圍 [first, last) 必須已經(jīng)根據(jù) comp 定義的標(biāo)準(zhǔn)進(jìn)行升序排序。 * pre 迭代器 Iter 必須滿足前向迭代器的要求。 * pre 比較器 Comp 必須滿足嚴(yán)格弱序。 */ template typename Iter, typename T, typename Comp std::lesstypename std::iterator_traitsIter::value_type bool binary_search_template(Iter first, Iter last, const T value, Comp comp Comp()) { // 使用 Iter low first; 和 Iter high last; 來(lái)界定當(dāng)前搜索區(qū)間 [low, high) Iter low first; Iter high last; // 循環(huán)條件搜索區(qū)間不為空。當(dāng) low high 時(shí)區(qū)間為空。 while (low ! high) { // 計(jì)算中間點(diǎn)。為了通用性使用 std::distance 和 std::advance。 // 注意對(duì)于非隨機(jī)訪問迭代器此操作可能非 O(1)但算法邏輯正確。 Iter mid low; std::advance(mid, std::distance(low, high) / 2); // 核心比較邏輯使用用戶提供的比較器 comp。 if (comp(*mid, value)) { // 情況1*mid value (根據(jù) comp 規(guī)則) // 目標(biāo)值只可能在右半部分 [std::next(mid), high) low std::next(mid); // 將搜索區(qū)間的左邊界移動(dòng)到 mid 的下一個(gè)位置 } else if (comp(value, *mid)) { // 情況2value *mid (根據(jù) comp 規(guī)則) // 目標(biāo)值只可能在左半部分 [low, mid) high mid; // 將搜索區(qū)間的右邊界移動(dòng)到 mid (因?yàn)閰^(qū)間右開) } else { // 情況3!comp(*mid, value) !comp(value, *mid) // 根據(jù)嚴(yán)格弱序這意味著 *mid 和 value 等價(jià)即找到了。 return true; } } // 循環(huán)結(jié)束仍未返回說(shuō)明搜索區(qū)間已為空未找到等價(jià)元素。 return false; }逐行解析與技巧typename std::iterator_traitsIter::value_type 這是獲取迭代器Iter所指向元素類型的標(biāo)準(zhǔn)方法。比直接假設(shè)typename Iter::value_type更通用因?yàn)樵羔樢部勺鳛榈鳑]有嵌套的value_type定義但iterator_traits對(duì)其有特化版本。Iter low first; Iter high last; 創(chuàng)建局部副本進(jìn)行操作避免修改傳入的迭代器參數(shù)這是良好的函數(shù)設(shè)計(jì)習(xí)慣。while (low ! high) 這是判斷區(qū)間[low, high)是否為空的經(jīng)典方式。比使用while (low high)更通用因?yàn)椴⒎撬械鞫贾С诌\(yùn)算符例如鏈表迭代器但所有迭代器都支持!比較。std::advance(mid, std::distance(low, high) / 2) 這是計(jì)算中間點(diǎn)的完全通用寫法。std::distance返回兩個(gè)迭代器之間的距離std::advance將迭代器移動(dòng)指定距離。注意性能對(duì)于隨機(jī)訪問迭代器如指針、vector::iteratordistance和advance是常數(shù)時(shí)間O(1)對(duì)于雙向或前向迭代器如list::iteratordistance是線性時(shí)間O(n)。在二分查找的循環(huán)中如果對(duì)非隨機(jī)訪問迭代器這樣計(jì)算會(huì)導(dǎo)致整體時(shí)間復(fù)雜度退化為O(n log n)甚至更差。因此在實(shí)踐文檔中必須明確指出該算法對(duì)隨機(jī)訪問迭代器才有對(duì)數(shù)復(fù)雜度。if (comp(*mid, value)) ... else if (comp(value, *mid)) ... else ... 這是實(shí)現(xiàn)比較的三段式。它完全依賴于比較器comp而不使用運(yùn)算符確保了與任何定義了嚴(yán)格弱序的比較規(guī)則兼容。low std::next(mid)與high mid 這是維護(hù)左閉右開區(qū)間[low, high)的關(guān)鍵。當(dāng)*mid value時(shí)mid及其左邊的元素都可以排除新的左邊界是mid的下一個(gè)位置(std::next(mid))。當(dāng)value *mid時(shí)mid及其右邊的元素都可以排除而由于區(qū)間右開新的右邊界正好是mid它本身不會(huì)被包含在新區(qū)間內(nèi)。5. 使用示例與場(chǎng)景拓展理論說(shuō)得再多不如看幾個(gè)實(shí)際的例子。下面演示如何在不同場(chǎng)景下使用我們的binary_search_template。5.1 基礎(chǔ)用法查找內(nèi)置類型#include iostream #include vector #include array int main() { // 示例1在 std::vectorint 中查找 std::vectorint vec {1, 3, 5, 7, 9, 11, 13, 15}; int target1 7; bool found1 binary_search_template(vec.begin(), vec.end(), target1); std::cout Target target1 (found1 ? found. : not found.) std::endl; // 輸出: Target 7 found. // 示例2在 C風(fēng)格數(shù)組 中查找 double arr[] {1.1, 2.2, 3.3, 4.4, 5.5}; double target2 3.3; bool found2 binary_search_template(std::begin(arr), std::end(arr), target2); std::cout Target target2 (found2 ? found. : not found.) std::endl; // 輸出: Target 3.3 found. // 示例3在 std::array 中查找 std::arraystd::string, 4 str_arr {apple, banana, orange, pear}; std::string target3 orange; // 默認(rèn)使用 std::lessstd::string即字典序比較 bool found3 binary_search_template(str_arr.begin(), str_arr.end(), target3); std::cout Target \ target3 \ (found3 ? found. : not found.) std::endl; // 輸出: Target orange found. return 0; }5.2 進(jìn)階用法自定義比較函數(shù)這是模板威力真正展現(xiàn)的地方。假設(shè)我們有一個(gè)Person結(jié)構(gòu)體我們想在不同的排序規(guī)則下進(jìn)行查找。#include string struct Person { std::string name; int age; double salary; }; int main() { std::vectorPerson people { {Alice, 30, 50000.0}, {Bob, 25, 45000.0}, {Charlie, 35, 60000.0}, {David, 28, 52000.0} }; // 首先必須根據(jù)比較規(guī)則對(duì)容器進(jìn)行排序 // 場(chǎng)景1按年齡升序查找 std::sort(people.begin(), people.end(), [](const Person a, const Person b) { return a.age b.age; }); Person target_by_age {, 28, 0.0}; // 我們只關(guān)心age字段用于查找 bool found_by_age binary_search_template( people.begin(), people.end(), target_by_age, [](const Person a, const Person b) { return a.age b.age; } // 比較年齡 ); std::cout Person with age 28 (found_by_age ? found. : not found.) std::endl; // 場(chǎng)景2按薪水降序查找 // 降序排序 std::sort(people.begin(), people.end(), [](const Person a, const Person b) { return a.salary b.salary; }); Person target_by_salary {, 0, 52000.0}; // 查找時(shí)比較器也必須對(duì)應(yīng)降序規(guī)則a.salary b.salary 意味著 a “小于” b // 不在二分查找中comp(a,b) 應(yīng)該反映排序時(shí)使用的“小于”關(guān)系。 // 我們排序用的是 return a.salary b.salary;這意味著“如果a.salary b.salary則a排在b前面”。 // 對(duì)于查找我們需要一個(gè)能判斷“是否排在前面”的函數(shù)。實(shí)際上排序用的lambda就是“小于”比較器在降序世界里。 // 更清晰的做法我們定義一個(gè)“小于”比較器它對(duì)于降序意味著“大于”。 // 可以這樣寫 auto desc_salary_comp [](const Person a, const Person b) { return a.salary b.salary; }; bool found_by_salary binary_search_template( people.begin(), people.end(), target_by_salary, desc_salary_comp ); std::cout Person with salary 52000 (found_by_salary ? found. : not found.) std::endl; return 0; }實(shí)操心得使用自定義比較器時(shí)排序所用的比較器與二分查找所用的比較器必須嚴(yán)格一致。這是導(dǎo)致查找失敗的最常見原因。一個(gè)好習(xí)慣是將比較器定義為一個(gè)單獨(dú)的變量如上面的desc_salary_comp然后同時(shí)傳遞給std::sort和binary_search_template確保完全一致。5.3 拓展場(chǎng)景二分答案的模板化應(yīng)用“二分答案”是算法競(jìng)賽和解決某些優(yōu)化問題的常用技巧。其核心是在一個(gè)單調(diào)或具有某種性質(zhì)的答案區(qū)間內(nèi)通過二分查找來(lái)尋找滿足條件的最優(yōu)解。我們的函數(shù)模板稍作修改就能適應(yīng)這種模式。假設(shè)我們有一個(gè)單調(diào)函數(shù)f(x)我們想找到最大的x使得f(x) target。我們可以對(duì)可能的x的取值區(qū)間進(jìn)行二分。// 一個(gè)判斷函數(shù)對(duì)于給定的x判斷條件是否成立 bool check(long long x, long long target) { // 假設(shè)這是一個(gè)計(jì)算量很大的函數(shù)例如計(jì)算x的某種代價(jià) long long calculated_value x * x; // 舉例f(x) x^2 return calculated_value target; } // 二分答案查找在區(qū)間 [low, high] 內(nèi)尋找滿足 check(x, target) 為真的最大 x。 long long binary_search_answer(long long low, long long high, long long target) { long long ans low - 1; // 初始化為不滿足條件的值 while (low high) { long long mid low (high - low) / 2; if (check(mid, target)) { // 條件滿足mid是一個(gè)候選答案記錄并嘗試更大的值 ans mid; low mid 1; } else { // 條件不滿足嘗試更小的值 high mid - 1; } } return ans; // 返回滿足條件的最大x } int main() { long long target 50; long long result binary_search_answer(0, 100, target); std::cout The largest x such that x^2 target is result std::endl; // 輸出: 7 return 0; }雖然這個(gè)例子沒有直接使用之前的函數(shù)模板因?yàn)椴僮鲗?duì)象是索引而非迭代器但其思想一脈相承。你可以很容易地將check函數(shù)抽象為一個(gè)可調(diào)用對(duì)象并模板化binary_search_answer函數(shù)使其適用于求解各種單調(diào)函數(shù)的最值問題。6. 常見問題、調(diào)試技巧與性能考量6.1 為什么我的二分查找總是返回false或進(jìn)入死循環(huán)這是實(shí)現(xiàn)二分查找時(shí)最常見的問題。根本原因通常出在區(qū)間定義和邊界更新上。區(qū)間定義不清晰你必須明確你維護(hù)的區(qū)間是左閉右開[first, last)還是左閉右閉[first, last]。我們的實(shí)現(xiàn)采用左閉右開因此循環(huán)條件為while (first ! last)。更新右邊界時(shí)last mid因?yàn)閙id已檢查且新區(qū)間不包含mid。更新左邊界時(shí)first std::next(mid)。邊界更新錯(cuò)誤最常見的錯(cuò)誤是left mid或right mid的誤用。記住一個(gè)原則新的搜索區(qū)間必須排除掉已經(jīng)確定不是目標(biāo)的mid位置。如果comp(*mid, value)為真*mid value那么mid及其左邊的所有元素都 value都不可能是目標(biāo)假設(shè)升序所以左邊界必須移到mid1。未排序或排序規(guī)則不一致二分查找的前提是區(qū)間有序。請(qǐng)務(wù)必確認(rèn)你的數(shù)據(jù)在使用binary_search_template之前已經(jīng)使用相同的比較規(guī)則進(jìn)行了排序。用std::sort排序然后用自定義比較器查找必須保證兩者一致。調(diào)試技巧在循環(huán)內(nèi)打印low、high、*mid的值觀察區(qū)間是如何縮小的。如果區(qū)間沒有按預(yù)期縮小或mid值不變化就能快速定位邏輯錯(cuò)誤。6.2 關(guān)于迭代器類型與性能的再討論我們的通用實(shí)現(xiàn)使用了std::distance和std::advance這保證了語(yǔ)法上的正確性。但我們必須清醒認(rèn)識(shí)到對(duì)于std::list、std::forward_list等容器它們的迭代器不是隨機(jī)訪問的。在這些容器上使用我們的通用二分查找std::distance的復(fù)雜度是O(n)。在二分查找的每次循環(huán)中都要計(jì)算一次這會(huì)導(dǎo)致總時(shí)間復(fù)雜度從理想的O(log n)惡化到O(n log n)這比線性遍歷O(n)還要慢因此二分查找的理想數(shù)據(jù)結(jié)構(gòu)是支持隨機(jī)訪問的如std::vector、std::deque、std::array和原生數(shù)組。對(duì)于鏈表應(yīng)避免使用二分查找。在實(shí)際的項(xiàng)目代碼中你可能會(huì)看到針對(duì)隨機(jī)訪問迭代器的特化版本它使用first (last - first) / 2來(lái)計(jì)算mid以獲得最佳性能。這可以通過模板特化或使用std::iterator_traits判斷迭代器類別來(lái)實(shí)現(xiàn)但這屬于更高級(jí)的模板元編程技巧。6.3 與STL中的二分查找算法對(duì)比C標(biāo)準(zhǔn)庫(kù)algorithm頭文件中已經(jīng)提供了幾個(gè)相關(guān)的二分查找函數(shù)std::binary_search 與我們的函數(shù)類似返回bool判斷是否存在。std::lower_bound 返回第一個(gè)不小于value的元素迭代器。std::upper_bound 返回第一個(gè)大于value的元素迭代器。std::equal_range 返回一個(gè)迭代器對(duì)表示等于value的元素范圍。我們的實(shí)現(xiàn)與std::binary_search有何異同相同點(diǎn) 核心算法邏輯、對(duì)有序區(qū)間和比較器的要求是一致的。不同點(diǎn)迭代器要求std::binary_search的迭代器要求是前向迭代器但實(shí)際實(shí)現(xiàn)可能會(huì)針對(duì)隨機(jī)訪問迭代器優(yōu)化。我們的通用實(shí)現(xiàn)明確展示了如何處理非隨機(jī)訪問迭代器盡管性能不佳。實(shí)現(xiàn)細(xì)節(jié) STL的實(shí)現(xiàn)經(jīng)過千錘百煉考慮了各種極端情況和編譯器優(yōu)化通常是最優(yōu)選擇。教育意義 自己實(shí)現(xiàn)一遍對(duì)于理解迭代器、模板、比較器和算法 invariants循環(huán)不變式有不可替代的作用。建議在生產(chǎn)代碼中優(yōu)先使用std::binary_search、std::lower_bound等標(biāo)準(zhǔn)庫(kù)算法。自己實(shí)現(xiàn)的模板更適合用于學(xué)習(xí)、定制特殊需求如返回索引而非迭代器或理解底層原理。6.4 模板的編譯與鏈接問題如果你將函數(shù)模板的聲明和實(shí)現(xiàn)分別放在.hpp和.cpp文件中可能會(huì)遇到“未定義的引用”鏈接錯(cuò)誤。這是因?yàn)槟０宀皇瞧胀ǖ暮瘮?shù)編譯器需要在看到模板定義而不僅僅是聲明的翻譯單元中根據(jù)具體的模板參數(shù)類型來(lái)實(shí)例化出具體的函數(shù)代碼。解決方案將模板的定義實(shí)現(xiàn)直接放在頭文件.hpp或.h中。這是最常見和推薦的做法。如果非要將實(shí)現(xiàn)放在.cpp文件則必須在.cpp文件末尾顯式實(shí)例化所有你可能用到的類型組合例如// binary_search_template.cpp template bool binary_search_templatestd::vectorint::iterator, int(std::vectorint::iterator, std::vectorint::iterator, const int); template bool binary_search_templatedouble*, double(double*, double*, const double); // ... 其他需要的實(shí)例化這種方法不靈活不推薦用于通用庫(kù)。將整個(gè)模板定義置于頭文件中意味著任何包含該頭文件的源文件在編譯時(shí)都能看到完整的定義從而可以實(shí)例化出所需的特定版本。這稍微增加了每個(gè)編譯單元的編譯時(shí)間但避免了鏈接錯(cuò)誤并保證了最大的靈活性。 C++二分查找函數(shù)模板：從算法到泛型編程的通用實(shí)現(xiàn)
1. 項(xiàng)目概述從“二分”到“函數(shù)模板”的通用化之旅在編程世界里“二分”是一個(gè)既古老又充滿活力的概念。無(wú)論是剛?cè)腴T的新手在力扣上刷題還是資深工程師在優(yōu)化海量數(shù)據(jù)查詢二分查找Binary Search都是繞不開的基石算法。它的核心思想簡(jiǎn)單而優(yōu)雅在一個(gè)有序的集合中通過不斷與中間元素比較將搜索范圍對(duì)半縮小從而以對(duì)數(shù)級(jí)的時(shí)間復(fù)雜度O(log n)快速定位目標(biāo)。然而當(dāng)我們從解決單一問題邁向構(gòu)建健壯、可復(fù)用的代碼庫(kù)時(shí)一個(gè)原始的二分查找實(shí)現(xiàn)就顯得捉襟見肘了。你可能會(huì)為整型數(shù)組寫一個(gè)版本為浮點(diǎn)數(shù)向量再寫一個(gè)為自定義結(jié)構(gòu)體又得重頭來(lái)過——代碼重復(fù)維護(hù)成本陡增。這正是“函數(shù)模板”大顯身手的地方。將“二分”與“函數(shù)模板”結(jié)合其核心目標(biāo)就是實(shí)現(xiàn)一個(gè)與數(shù)據(jù)類型無(wú)關(guān)的、通用的二分查找算法。它不再僅僅是一個(gè)解決特定問題的代碼片段而是一個(gè)可以被復(fù)用的“工具”。無(wú)論你的數(shù)據(jù)是int、double、std::string還是你自己定義的Student對(duì)象只要這些數(shù)據(jù)能夠被比較即定義了或等操作這個(gè)模板化的二分函數(shù)就能無(wú)縫工作。這背后體現(xiàn)的是泛型編程Generic Programming的思想將算法與數(shù)據(jù)結(jié)構(gòu)分離讓算法獨(dú)立于任何特定的數(shù)據(jù)類型。對(duì)于初學(xué)者理解這個(gè)組合能幫你跨越“會(huì)寫算法”到“會(huì)設(shè)計(jì)通用工具”的鴻溝對(duì)于有經(jīng)驗(yàn)的開發(fā)者一個(gè)精心打磨的二分函數(shù)模板是工具箱里的瑞士軍刀能在各種場(chǎng)景下快速部署提升開發(fā)效率與代碼質(zhì)量。接下來(lái)我們就深入拆解如何構(gòu)建這樣一個(gè)既強(qiáng)大又靈活的二分查找函數(shù)模板。2. 核心思路與設(shè)計(jì)考量2.1 為何需要模板化從具體到抽象的必然假設(shè)我們有一個(gè)最簡(jiǎn)單的整型數(shù)組二分查找int binarySearch_int(int arr[], int size, int target) { int left 0, right size - 1; while (left right) { int mid left (right - left) / 2; // 防止溢出 if (arr[mid] target) return mid; else if (arr[mid] target) left mid 1; else right mid - 1; } return -1; // 未找到 }這個(gè)函數(shù)工作得很好但局限性也顯而易見它只能處理int類型的數(shù)組。如果明天需要處理std::vectordouble你就得復(fù)制一份代碼把所有的int改成double。這種重復(fù)不僅枯燥更危險(xiǎn)的是當(dāng)你發(fā)現(xiàn)原函數(shù)有一個(gè)邊界條件bug時(shí)你需要記住在所有拷貝的版本中進(jìn)行同樣的修改極易出錯(cuò)。函數(shù)模板通過引入一個(gè)“類型參數(shù)”來(lái)解決這個(gè)問題。你可以把類型參數(shù)T想象成一個(gè)占位符編譯器會(huì)在你調(diào)用函數(shù)時(shí)用實(shí)際的類型如int、double來(lái)替換它自動(dòng)為你生成對(duì)應(yīng)類型的函數(shù)版本。這樣你只需維護(hù)一份源代碼。2.2 設(shè)計(jì)決策迭代器與比較函數(shù)的引入一個(gè)工業(yè)級(jí)的二分函數(shù)模板絕不會(huì)僅僅滿足于處理內(nèi)置類型的數(shù)組。它的設(shè)計(jì)需要更普適。這里有兩個(gè)關(guān)鍵的設(shè)計(jì)決策1. 使用迭代器Iterators而非原生指針或容器我們最初的例子使用了C風(fēng)格數(shù)組和指針運(yùn)算。但在現(xiàn)代C中標(biāo)準(zhǔn)庫(kù)容器如vector,list,array和算法都基于迭代器設(shè)計(jì)。迭代器是一種抽象它統(tǒng)一了對(duì)不同數(shù)據(jù)結(jié)構(gòu)連續(xù)內(nèi)存如數(shù)組或非連續(xù)內(nèi)存如鏈表的訪問方式。我們的二分模板如果接受一對(duì)迭代器[first, last)來(lái)表示搜索范圍那么它將能應(yīng)用于所有標(biāo)準(zhǔn)庫(kù)順序容器vector,deque,array,list的部分操作原生數(shù)組甚至用戶自定義的、提供了迭代器的容器 這極大地?cái)U(kuò)展了函數(shù)的適用范圍。[first, last)是一個(gè)左閉右開區(qū)間這是STL的慣例使得表示空范圍first last和計(jì)算元素?cái)?shù)量last - first都非常自然。2. 支持自定義比較函數(shù)Comparator標(biāo)準(zhǔn)的二分查找要求數(shù)據(jù)有序。但“有序”的標(biāo)準(zhǔn)是什么對(duì)于整數(shù)是數(shù)值大小對(duì)于字符串可能是字典序?qū)τ谧远x的Person對(duì)象你可能想按年齡或姓名排序。因此一個(gè)通用的二分函數(shù)必須允許用戶傳入一個(gè)自定義的比較準(zhǔn)則。 通常我們提供一個(gè)默認(rèn)參數(shù)為std::lessT()它使用類型的運(yùn)算符。同時(shí)允許用戶傳入任何可調(diào)用對(duì)象函數(shù)指針、函數(shù)對(duì)象、lambda表達(dá)式來(lái)定義自己的“小于”關(guān)系。這使得模板不僅能查找值還能用于更復(fù)雜的場(chǎng)景比如在單調(diào)函數(shù)上查找滿足某個(gè)條件的第一個(gè)位置二分答案的思想。注意比較函數(shù)必須與排序時(shí)使用的比較規(guī)則一致否則二分查找的前提有序性被破壞結(jié)果將不可預(yù)測(cè)。這是使用自定義比較器時(shí)最容易踩的坑?；谝陨峡剂课覀兡繕?biāo)函數(shù)的原型逐漸清晰templatetypename Iter, typename T, typename Comp bool binary_search(Iter first, Iter last, const T value, Comp comp)。3. 核心細(xì)節(jié)解析與實(shí)現(xiàn)要點(diǎn)3.1 函數(shù)模板的語(yǔ)法骨架首先我們搭建模板的聲明部分。這里需要聲明三個(gè)模板參數(shù)typename Iter迭代器類型代表數(shù)據(jù)序列的訪問方式。typename T要查找的值的類型。注意這個(gè)類型不一定與迭代器解引用后的類型完全相同但必須能與之間接比較通過Comp。typename Comp比較函數(shù)對(duì)象的類型默認(rèn)使用std::lesstypename std::iterator_traitsIter::value_type。這里用到了std::iterator_traits來(lái)安全地獲取迭代器指向的元素類型比直接假設(shè)更魯棒。#include iterator // for iterator_traits #include functional // for less template typename Iter, typename T, typename Comp std::lesstypename std::iterator_traitsIter::value_type bool binary_search_template(Iter first, Iter last, const T value, Comp comp Comp()) { // 實(shí)現(xiàn)細(xì)節(jié)將在下文展開 }3.2 迭代器運(yùn)算與“中間點(diǎn)”的計(jì)算在循環(huán)體內(nèi)我們需要計(jì)算當(dāng)前搜索范圍的中間點(diǎn)。對(duì)于像vector這樣的隨機(jī)訪問迭代器我們可以直接用first (last - first) / 2。但對(duì)于像list這樣的雙向迭代器這種加減法是無(wú)效的。為了寫出真正通用的代碼我們不能直接對(duì)迭代器進(jìn)行加法。正確的通用做法是使用std::distance(first, last)計(jì)算區(qū)間長(zhǎng)度。這個(gè)函數(shù)對(duì)于隨機(jī)訪問迭代器是O(1)對(duì)于其他迭代器是O(n)但在二分查找的上下文中我們通常假設(shè)迭代器至少是前向迭代器且distance只在循環(huán)外或邏輯判斷中使用影響不大。使用std::advance將迭代器移動(dòng)特定的距離。更常見的寫法是先復(fù)制first迭代器然后移動(dòng)它的副本。在實(shí)際的二分查找實(shí)現(xiàn)中我們通常采用一種不直接計(jì)算總長(zhǎng)度的方法它適用于任何前向迭代器雖然對(duì)于非隨機(jī)訪問迭代器效率低但語(yǔ)法正確while (first ! last) { Iter mid first; std::advance(mid, std::distance(first, last) / 2); // ... 比較邏輯 }然而對(duì)于二分查找我們通常期望在隨機(jī)訪問數(shù)據(jù)結(jié)構(gòu)上使用以獲得O(log n)的性能。因此在文檔或接口約定中可以注明“該函數(shù)對(duì)迭代器類別的要求為隨機(jī)訪問迭代器”并在實(shí)現(xiàn)中使用first (last - first) / 2這種高效形式。這是一種在通用性和性能之間的權(quán)衡。為了教學(xué)和通用性我們先展示完全通用的版本但需要明白其潛在的性能影響。3.3 比較邏輯與邊界移動(dòng)這是二分查找的核心邏輯。我們需要用傳入的comp函數(shù)對(duì)象來(lái)比較*mid和value。如果comp(*mid, value)為真意味著*mid value根據(jù)自定義規(guī)則那么目標(biāo)值只可能在后半段移動(dòng)first std::next(mid)。如果comp(value, *mid)為真意味著value *mid那么目標(biāo)值只可能在前半段移動(dòng)last mid。如果兩者都為假根據(jù)邏輯意味著!comp(*mid, value) !comp(value, *mid)這通常等價(jià)于*mid value在嚴(yán)格弱序下此時(shí)我們找到了目標(biāo)。這里有一個(gè)極其重要的細(xì)節(jié)我們不應(yīng)該直接使用*mid value來(lái)判斷相等。因?yàn)橛脩艨赡軅魅肓艘粋€(gè)自定義的比較器它定義的“等價(jià)”不等于operator。在嚴(yán)格弱序中兩個(gè)元素a和b“等價(jià)”的定義是!comp(a, b) !comp(b, a)。我們的查找函數(shù)應(yīng)該遵循這個(gè)定義這樣才能與STL的std::binary_search等算法保持行為一致。3.4 返回值的設(shè)計(jì)基礎(chǔ)的二分查找通常返回找到元素的索引或迭代器。我們的模板示例返回bool表示是否存在。這是一種簡(jiǎn)潔的設(shè)計(jì)。你也可以設(shè)計(jì)為返回迭代器找到時(shí)返回指向該元素的迭代器未找到時(shí)返回last這樣調(diào)用者能獲得更多信息。STL的std::lower_bound就是返回迭代器的典范它返回第一個(gè)不小于value的元素位置可以同時(shí)用于查找和插入。在我們的實(shí)現(xiàn)中為了聚焦于模板本身先采用返回bool的簡(jiǎn)單形式。4. 完整實(shí)現(xiàn)與逐行解析結(jié)合以上所有要點(diǎn)我們給出一個(gè)完整、健壯且?guī)в性敿?xì)注釋的二分查找函數(shù)模板實(shí)現(xiàn)。#include iterator #include functional /** * brief 通用的二分查找函數(shù)模板。 * * tparam Iter 前向迭代器類型至少支持前向遍歷。對(duì)于隨機(jī)訪問迭代器有最佳性能。 * tparam T 要查找的值的類型。 * tparam Comp 比較函數(shù)對(duì)象類型默認(rèn)使用 std::less迭代器值類型。 * param first 搜索范圍的起始迭代器包含。 * param last 搜索范圍的結(jié)束迭代器不包含。 * param value 要查找的目標(biāo)值。 * param comp 用于比較的函數(shù)對(duì)象默認(rèn)為 Comp()。 * return true 如果在范圍 [first, last) 中找到等價(jià)于 value 的元素。 * return false 否則。 * * pre 范圍 [first, last) 必須已經(jīng)根據(jù) comp 定義的標(biāo)準(zhǔn)進(jìn)行升序排序。 * pre 迭代器 Iter 必須滿足前向迭代器的要求。 * pre 比較器 Comp 必須滿足嚴(yán)格弱序。 */ template typename Iter, typename T, typename Comp std::lesstypename std::iterator_traitsIter::value_type bool binary_search_template(Iter first, Iter last, const T value, Comp comp Comp()) { // 使用 Iter low first; 和 Iter high last; 來(lái)界定當(dāng)前搜索區(qū)間 [low, high) Iter low first; Iter high last; // 循環(huán)條件搜索區(qū)間不為空。當(dāng) low high 時(shí)區(qū)間為空。 while (low ! high) { // 計(jì)算中間點(diǎn)。為了通用性使用 std::distance 和 std::advance。 // 注意對(duì)于非隨機(jī)訪問迭代器此操作可能非 O(1)但算法邏輯正確。 Iter mid low; std::advance(mid, std::distance(low, high) / 2); // 核心比較邏輯使用用戶提供的比較器 comp。 if (comp(*mid, value)) { // 情況1*mid value (根據(jù) comp 規(guī)則) // 目標(biāo)值只可能在右半部分 [std::next(mid), high) low std::next(mid); // 將搜索區(qū)間的左邊界移動(dòng)到 mid 的下一個(gè)位置 } else if (comp(value, *mid)) { // 情況2value *mid (根據(jù) comp 規(guī)則) // 目標(biāo)值只可能在左半部分 [low, mid) high mid; // 將搜索區(qū)間的右邊界移動(dòng)到 mid (因?yàn)閰^(qū)間右開) } else { // 情況3!comp(*mid, value) !comp(value, *mid) // 根據(jù)嚴(yán)格弱序這意味著 *mid 和 value 等價(jià)即找到了。 return true; } } // 循環(huán)結(jié)束仍未返回說(shuō)明搜索區(qū)間已為空未找到等價(jià)元素。 return false; }逐行解析與技巧typename std::iterator_traitsIter::value_type 這是獲取迭代器Iter所指向元素類型的標(biāo)準(zhǔn)方法。比直接假設(shè)typename Iter::value_type更通用因?yàn)樵羔樢部勺鳛榈鳑]有嵌套的value_type定義但iterator_traits對(duì)其有特化版本。Iter low first; Iter high last; 創(chuàng)建局部副本進(jìn)行操作避免修改傳入的迭代器參數(shù)這是良好的函數(shù)設(shè)計(jì)習(xí)慣。while (low ! high) 這是判斷區(qū)間[low, high)是否為空的經(jīng)典方式。比使用while (low high)更通用因?yàn)椴⒎撬械鞫贾С诌\(yùn)算符例如鏈表迭代器但所有迭代器都支持!比較。std::advance(mid, std::distance(low, high) / 2) 這是計(jì)算中間點(diǎn)的完全通用寫法。std::distance返回兩個(gè)迭代器之間的距離std::advance將迭代器移動(dòng)指定距離。注意性能對(duì)于隨機(jī)訪問迭代器如指針、vector::iteratordistance和advance是常數(shù)時(shí)間O(1)對(duì)于雙向或前向迭代器如list::iteratordistance是線性時(shí)間O(n)。在二分查找的循環(huán)中如果對(duì)非隨機(jī)訪問迭代器這樣計(jì)算會(huì)導(dǎo)致整體時(shí)間復(fù)雜度退化為O(n log n)甚至更差。因此在實(shí)踐文檔中必須明確指出該算法對(duì)隨機(jī)訪問迭代器才有對(duì)數(shù)復(fù)雜度。if (comp(*mid, value)) ... else if (comp(value, *mid)) ... else ... 這是實(shí)現(xiàn)比較的三段式。它完全依賴于比較器comp而不使用運(yùn)算符確保了與任何定義了嚴(yán)格弱序的比較規(guī)則兼容。low std::next(mid)與high mid 這是維護(hù)左閉右開區(qū)間[low, high)的關(guān)鍵。當(dāng)*mid value時(shí)mid及其左邊的元素都可以排除新的左邊界是mid的下一個(gè)位置(std::next(mid))。當(dāng)value *mid時(shí)mid及其右邊的元素都可以排除而由于區(qū)間右開新的右邊界正好是mid它本身不會(huì)被包含在新區(qū)間內(nèi)。5. 使用示例與場(chǎng)景拓展理論說(shuō)得再多不如看幾個(gè)實(shí)際的例子。下面演示如何在不同場(chǎng)景下使用我們的binary_search_template。5.1 基礎(chǔ)用法查找內(nèi)置類型#include iostream #include vector #include array int main() { // 示例1在 std::vectorint 中查找 std::vectorint vec {1, 3, 5, 7, 9, 11, 13, 15}; int target1 7; bool found1 binary_search_template(vec.begin(), vec.end(), target1); std::cout Target target1 (found1 ? found. : not found.) std::endl; // 輸出: Target 7 found. // 示例2在 C風(fēng)格數(shù)組 中查找 double arr[] {1.1, 2.2, 3.3, 4.4, 5.5}; double target2 3.3; bool found2 binary_search_template(std::begin(arr), std::end(arr), target2); std::cout Target target2 (found2 ? found. : not found.) std::endl; // 輸出: Target 3.3 found. // 示例3在 std::array 中查找 std::arraystd::string, 4 str_arr {apple, banana, orange, pear}; std::string target3 orange; // 默認(rèn)使用 std::lessstd::string即字典序比較 bool found3 binary_search_template(str_arr.begin(), str_arr.end(), target3); std::cout Target \ target3 \ (found3 ? found. : not found.) std::endl; // 輸出: Target orange found. return 0; }5.2 進(jìn)階用法自定義比較函數(shù)這是模板威力真正展現(xiàn)的地方。假設(shè)我們有一個(gè)Person結(jié)構(gòu)體我們想在不同的排序規(guī)則下進(jìn)行查找。#include string struct Person { std::string name; int age; double salary; }; int main() { std::vectorPerson people { {Alice, 30, 50000.0}, {Bob, 25, 45000.0}, {Charlie, 35, 60000.0}, {David, 28, 52000.0} }; // 首先必須根據(jù)比較規(guī)則對(duì)容器進(jìn)行排序 // 場(chǎng)景1按年齡升序查找 std::sort(people.begin(), people.end(), [](const Person a, const Person b) { return a.age b.age; }); Person target_by_age {, 28, 0.0}; // 我們只關(guān)心age字段用于查找 bool found_by_age binary_search_template( people.begin(), people.end(), target_by_age, [](const Person a, const Person b) { return a.age b.age; } // 比較年齡 ); std::cout Person with age 28 (found_by_age ? found. : not found.) std::endl; // 場(chǎng)景2按薪水降序查找 // 降序排序 std::sort(people.begin(), people.end(), [](const Person a, const Person b) { return a.salary b.salary; }); Person target_by_salary {, 0, 52000.0}; // 查找時(shí)比較器也必須對(duì)應(yīng)降序規(guī)則a.salary b.salary 意味著 a “小于” b // 不在二分查找中comp(a,b) 應(yīng)該反映排序時(shí)使用的“小于”關(guān)系。 // 我們排序用的是 return a.salary b.salary;這意味著“如果a.salary b.salary則a排在b前面”。 // 對(duì)于查找我們需要一個(gè)能判斷“是否排在前面”的函數(shù)。實(shí)際上排序用的lambda就是“小于”比較器在降序世界里。 // 更清晰的做法我們定義一個(gè)“小于”比較器它對(duì)于降序意味著“大于”。 // 可以這樣寫 auto desc_salary_comp [](const Person a, const Person b) { return a.salary b.salary; }; bool found_by_salary binary_search_template( people.begin(), people.end(), target_by_salary, desc_salary_comp ); std::cout Person with salary 52000 (found_by_salary ? found. : not found.) std::endl; return 0; }實(shí)操心得使用自定義比較器時(shí)排序所用的比較器與二分查找所用的比較器必須嚴(yán)格一致。這是導(dǎo)致查找失敗的最常見原因。一個(gè)好習(xí)慣是將比較器定義為一個(gè)單獨(dú)的變量如上面的desc_salary_comp然后同時(shí)傳遞給std::sort和binary_search_template確保完全一致。5.3 拓展場(chǎng)景二分答案的模板化應(yīng)用“二分答案”是算法競(jìng)賽和解決某些優(yōu)化問題的常用技巧。其核心是在一個(gè)單調(diào)或具有某種性質(zhì)的答案區(qū)間內(nèi)通過二分查找來(lái)尋找滿足條件的最優(yōu)解。我們的函數(shù)模板稍作修改就能適應(yīng)這種模式。假設(shè)我們有一個(gè)單調(diào)函數(shù)f(x)我們想找到最大的x使得f(x) target。我們可以對(duì)可能的x的取值區(qū)間進(jìn)行二分。// 一個(gè)判斷函數(shù)對(duì)于給定的x判斷條件是否成立 bool check(long long x, long long target) { // 假設(shè)這是一個(gè)計(jì)算量很大的函數(shù)例如計(jì)算x的某種代價(jià) long long calculated_value x * x; // 舉例f(x) x^2 return calculated_value target; } // 二分答案查找在區(qū)間 [low, high] 內(nèi)尋找滿足 check(x, target) 為真的最大 x。 long long binary_search_answer(long long low, long long high, long long target) { long long ans low - 1; // 初始化為不滿足條件的值 while (low high) { long long mid low (high - low) / 2; if (check(mid, target)) { // 條件滿足mid是一個(gè)候選答案記錄并嘗試更大的值 ans mid; low mid 1; } else { // 條件不滿足嘗試更小的值 high mid - 1; } } return ans; // 返回滿足條件的最大x } int main() { long long target 50; long long result binary_search_answer(0, 100, target); std::cout The largest x such that x^2 target is result std::endl; // 輸出: 7 return 0; }雖然這個(gè)例子沒有直接使用之前的函數(shù)模板因?yàn)椴僮鲗?duì)象是索引而非迭代器但其思想一脈相承。你可以很容易地將check函數(shù)抽象為一個(gè)可調(diào)用對(duì)象并模板化binary_search_answer函數(shù)使其適用于求解各種單調(diào)函數(shù)的最值問題。6. 常見問題、調(diào)試技巧與性能考量6.1 為什么我的二分查找總是返回false或進(jìn)入死循環(huán)這是實(shí)現(xiàn)二分查找時(shí)最常見的問題。根本原因通常出在區(qū)間定義和邊界更新上。區(qū)間定義不清晰你必須明確你維護(hù)的區(qū)間是左閉右開[first, last)還是左閉右閉[first, last]。我們的實(shí)現(xiàn)采用左閉右開因此循環(huán)條件為while (first ! last)。更新右邊界時(shí)last mid因?yàn)閙id已檢查且新區(qū)間不包含mid。更新左邊界時(shí)first std::next(mid)。邊界更新錯(cuò)誤最常見的錯(cuò)誤是left mid或right mid的誤用。記住一個(gè)原則新的搜索區(qū)間必須排除掉已經(jīng)確定不是目標(biāo)的mid位置。如果comp(*mid, value)為真*mid value那么mid及其左邊的所有元素都 value都不可能是目標(biāo)假設(shè)升序所以左邊界必須移到mid1。未排序或排序規(guī)則不一致二分查找的前提是區(qū)間有序。請(qǐng)務(wù)必確認(rèn)你的數(shù)據(jù)在使用binary_search_template之前已經(jīng)使用相同的比較規(guī)則進(jìn)行了排序。用std::sort排序然后用自定義比較器查找必須保證兩者一致。調(diào)試技巧在循環(huán)內(nèi)打印low、high、*mid的值觀察區(qū)間是如何縮小的。如果區(qū)間沒有按預(yù)期縮小或mid值不變化就能快速定位邏輯錯(cuò)誤。6.2 關(guān)于迭代器類型與性能的再討論我們的通用實(shí)現(xiàn)使用了std::distance和std::advance這保證了語(yǔ)法上的正確性。但我們必須清醒認(rèn)識(shí)到對(duì)于std::list、std::forward_list等容器它們的迭代器不是隨機(jī)訪問的。在這些容器上使用我們的通用二分查找std::distance的復(fù)雜度是O(n)。在二分查找的每次循環(huán)中都要計(jì)算一次這會(huì)導(dǎo)致總時(shí)間復(fù)雜度從理想的O(log n)惡化到O(n log n)這比線性遍歷O(n)還要慢因此二分查找的理想數(shù)據(jù)結(jié)構(gòu)是支持隨機(jī)訪問的如std::vector、std::deque、std::array和原生數(shù)組。對(duì)于鏈表應(yīng)避免使用二分查找。在實(shí)際的項(xiàng)目代碼中你可能會(huì)看到針對(duì)隨機(jī)訪問迭代器的特化版本它使用first (last - first) / 2來(lái)計(jì)算mid以獲得最佳性能。這可以通過模板特化或使用std::iterator_traits判斷迭代器類別來(lái)實(shí)現(xiàn)但這屬于更高級(jí)的模板元編程技巧。6.3 與STL中的二分查找算法對(duì)比C標(biāo)準(zhǔn)庫(kù)algorithm頭文件中已經(jīng)提供了幾個(gè)相關(guān)的二分查找函數(shù)std::binary_search 與我們的函數(shù)類似返回bool判斷是否存在。std::lower_bound 返回第一個(gè)不小于value的元素迭代器。std::upper_bound 返回第一個(gè)大于value的元素迭代器。std::equal_range 返回一個(gè)迭代器對(duì)表示等于value的元素范圍。我們的實(shí)現(xiàn)與std::binary_search有何異同相同點(diǎn) 核心算法邏輯、對(duì)有序區(qū)間和比較器的要求是一致的。不同點(diǎn)迭代器要求std::binary_search的迭代器要求是前向迭代器但實(shí)際實(shí)現(xiàn)可能會(huì)針對(duì)隨機(jī)訪問迭代器優(yōu)化。我們的通用實(shí)現(xiàn)明確展示了如何處理非隨機(jī)訪問迭代器盡管性能不佳。實(shí)現(xiàn)細(xì)節(jié) STL的實(shí)現(xiàn)經(jīng)過千錘百煉考慮了各種極端情況和編譯器優(yōu)化通常是最優(yōu)選擇。教育意義 自己實(shí)現(xiàn)一遍對(duì)于理解迭代器、模板、比較器和算法 invariants循環(huán)不變式有不可替代的作用。建議在生產(chǎn)代碼中優(yōu)先使用std::binary_search、std::lower_bound等標(biāo)準(zhǔn)庫(kù)算法。自己實(shí)現(xiàn)的模板更適合用于學(xué)習(xí)、定制特殊需求如返回索引而非迭代器或理解底層原理。6.4 模板的編譯與鏈接問題如果你將函數(shù)模板的聲明和實(shí)現(xiàn)分別放在.hpp和.cpp文件中可能會(huì)遇到“未定義的引用”鏈接錯(cuò)誤。這是因?yàn)槟０宀皇瞧胀ǖ暮瘮?shù)編譯器需要在看到模板定義而不僅僅是聲明的翻譯單元中根據(jù)具體的模板參數(shù)類型來(lái)實(shí)例化出具體的函數(shù)代碼。解決方案將模板的定義實(shí)現(xiàn)直接放在頭文件.hpp或.h中。這是最常見和推薦的做法。如果非要將實(shí)現(xiàn)放在.cpp文件則必須在.cpp文件末尾顯式實(shí)例化所有你可能用到的類型組合例如// binary_search_template.cpp template bool binary_search_templatestd::vectorint::iterator, int(std::vectorint::iterator, std::vectorint::iterator, const int); template bool binary_search_templatedouble*, double(double*, double*, const double); // ... 其他需要的實(shí)例化這種方法不靈活不推薦用于通用庫(kù)。將整個(gè)模板定義置于頭文件中意味著任何包含該頭文件的源文件在編譯時(shí)都能看到完整的定義從而可以實(shí)例化出所需的特定版本。這稍微增加了每個(gè)編譯單元的編譯時(shí)間但避免了鏈接錯(cuò)誤并保證了最大的靈活性。