分治法(Divide and Conquer)和二分法(Binary Search)都是十分重要的算法思想。

分治法可以將較大規(guī)模的問(wèn)題，拆分為若干與原問(wèn)題相似的問(wèn)題，求解后合并到原問(wèn)題，從而優(yōu)化復(fù)雜度。

二分法，一般是對(duì)于一個(gè)具有單調(diào)性的函數(shù)求某個(gè)分界點(diǎn)。

本文將講解對(duì)于分治法/二分法的本質(zhì)理解，全是干貨，歡迎細(xì)品。

課程大綱：https://www.eriktse.com/algorithm/1215.html

?? 作者：Eriktse
??? 簡(jiǎn)介：211計(jì)算機(jī)在讀，CCPC全國(guó)賽金牌，ICPC區(qū)域賽銀牌退役選手??力爭(zhēng)以通俗易懂的方式講解編程和算法！??歡迎關(guān)注我，一起交流C++/Python算法。（優(yōu)質(zhì)好文持續(xù)更新中……）??
???歡迎加群一起玩耍~QQ群：600240150

分治法

運(yùn)用分治法需要滿(mǎn)足以下條件：

1.該問(wèn)題的規(guī)?？s小到一定的程度就可以容易的解決。
2.該問(wèn)題可以分解為若干個(gè)規(guī)模較小的相同問(wèn)題，即該問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。
3.利用該問(wèn)題分解出的子問(wèn)題的解可以合并為該問(wèn)題的解。
4.該問(wèn)題所分解出的各個(gè)子問(wèn)題是相互獨(dú)立的，即子問(wèn)題之間不包含公共的子問(wèn)題。

引用自：https://zhuanlan.zhihu.com/p/72734354

簡(jiǎn)單了解以上條件后，我們來(lái)講一下分治法的思維步驟 ：

確定問(wèn)題模型

通過(guò)閱讀題意，將題意所求轉(zhuǎn)換為一個(gè)數(shù)學(xué)模型。

比如將題目所求的東西轉(zhuǎn)換為求數(shù)組的一段區(qū)間的和，或者是求某個(gè)函數(shù)的臨界點(diǎn)，或是求某個(gè)函數(shù)的極大值、極小值，這個(gè)一般比較容易分析。

確定拆分（合并）性質(zhì)

比如題目要求數(shù)組的某個(gè)區(qū)間[l, r]的和，其實(shí)可以轉(zhuǎn)換為[l, mid]的和再加上[mid + 1, r]的和。

我們可以發(fā)現(xiàn)[l, mid]和[mid + 1, r]這兩個(gè)區(qū)間是可以從[l, r]拆分出來(lái)且相互獨(dú)立的，并且滿(mǎn)足合并的性質(zhì)：

這是顯然的，如果你想看更多關(guān)于和式的知識(shí)，歡迎閱讀《【ACM數(shù)論】和式變換技術(shù)，也許是最好的講解之一》。

再或者，在歸并排序中，題目要求你將區(qū)間[l, r]排序，我們就可以將兩個(gè)子區(qū)間[l, mid]，[mid + 1,r]排序后進(jìn)行合并。

我們可以發(fā)現(xiàn)，我們?cè)趧澐值臅r(shí)候，盡量都從中間劃分，因?yàn)檫@樣可以使得復(fù)雜度盡可能低，并且劃分出來(lái)的子問(wèn)題正好可以填滿(mǎn)原問(wèn)題并且沒(méi)有重疊、支持合并。

上面的例子合并起來(lái)都很簡(jiǎn)單，但是往往我們做題的時(shí)候，會(huì)在合并過(guò)程中處理一些東西，來(lái)得到答案?；蚴窍駱?shù)形DP一樣，將子狀態(tài)向上轉(zhuǎn)移的時(shí)候需要做一些處理?？傊治龀稣_的合并公式是十分關(guān)鍵的！

確定分治終點(diǎn)的解法

在分治終點(diǎn)，一般是規(guī)模極小的問(wèn)題，比如求一個(gè)長(zhǎng)度為2的區(qū)間的和，或者將一個(gè)長(zhǎng)度為2的區(qū)間排序。這個(gè)就很容易寫(xiě)了。

小結(jié)

分治法往往會(huì)生成一棵樹(shù)，每一個(gè)子問(wèn)題就是樹(shù)上的一個(gè)節(jié)點(diǎn)，我們從根節(jié)點(diǎn)出發(fā)，自頂向下分解問(wèn)題，也就是從兒子上面找答案，當(dāng)某個(gè)點(diǎn)問(wèn)題足夠簡(jiǎn)單了，就直接處理，然后向上更新。

二分法

其實(shí)二分法應(yīng)該是屬于分治的一種，但是由于在很多時(shí)候，習(xí)慣于將其分開(kāi)，且他們的思維過(guò)程有比較大的區(qū)別，所以我們單獨(dú)拎出來(lái)講。

二分法一般用于求解一個(gè)具有單調(diào)性的函數(shù)的分界點(diǎn)。

研究單調(diào)性

公式顯示不全，請(qǐng)移步：https://www.eriktse.com/algorithm/1231.html

或知乎文章：https://zhuanlan.zhihu.com/p/634626310

在二分之前，需要研究函數(shù)的單調(diào)性。比如我們要求在正整數(shù)定義域內(nèi)函數(shù)滿(mǎn)足：

的最小的，其中一般是個(gè)定值。

我們?nèi)菀装l(fā)現(xiàn)在正整數(shù)定義域內(nèi)是單調(diào)遞增的。

對(duì)于其他函數(shù)也是類(lèi)似的進(jìn)行單調(diào)性分析。

確定枚舉區(qū)間

在進(jìn)行二分之前，我們需要確定枚舉的區(qū)間。

我們用l表示左指針，r表示右指針，mid為(l + r) / 2。

我們的答案一定會(huì)在區(qū)間[l, r]內(nèi)，所以我們需要選取合適的區(qū)間才能保證找到答案。

上面這個(gè)例題，我們可以選取l = 0，r = inf。（inf是無(wú)窮大的意思）。

這個(gè)無(wú)窮大我們可以取到8e18（8乘10的18次方）。因?yàn)槲覀冎溃?/p>

確定判斷函數(shù)

二分實(shí)際上也是一種枚舉，不是在枚舉過(guò)程中，我們通過(guò)數(shù)學(xué)規(guī)律舍棄了很大一部分無(wú)效解。

在枚舉出一個(gè)解后，需要通過(guò)判斷函數(shù)（我們一般命名為check()），來(lái)判斷解屬于那一部分（在這個(gè)例子中，就是劃分為<m和>=m兩部分），然后決定l, r的移動(dòng)。

確定答案

和題意結(jié)合，輸出對(duì)應(yīng)的答案，這一步尤其要注意，要理解清楚題目的意思，比如第一個(gè)大于等于的，最后一個(gè)小于的，最后一個(gè)小于等于的等等等等。需要自己多加小心。

例題

ETOJ 1017: 求逆序?qū)€(gè)數(shù)

鏈接：http://cdn.oj.eriktse.com/problem.php?id=1017

分治法，每次將子區(qū)間排序后，將兩個(gè)排序區(qū)間合并，在合并過(guò)程中可以處理出逆序?qū)€(gè)數(shù)。

對(duì)于兩個(gè)已經(jīng)排序的數(shù)組，新產(chǎn)生的逆序?qū)Φ膫€(gè)數(shù)就是從右邊區(qū)間取出元素時(shí)，左邊區(qū)間剩余的元素的個(gè)數(shù)cnt。因?yàn)檫@樣表示在原數(shù)組中有cnt個(gè)元素，滿(mǎn)足下標(biāo)小，值大的特性。

ETOJ 1013: 小e的書(shū)架

鏈接：http://cdn.oj.eriktse.com/problem.php?id=1013

這題的題解可以用二分法做，也可以直接數(shù)學(xué)方法做，具體看這里（E題）：https://www.eriktse.com/algorithm/1224.html