新的角度看二分

• 二分就是將數(shù)組分為兩段
• 因此，問(wèn)題的最終目標(biāo)是找出藍(lán)紅邊界

樸素算法

• 紅色指針一開(kāi)始指向最右超出范圍處，隨后不斷向左移動(dòng)，直到找到藍(lán)紅邊界；或者藍(lán)色指針…
• 時(shí)間復(fù)雜度$O(n)$

二分查找

• 紅藍(lán)指針的移動(dòng)其實(shí)代表著紅藍(lán)區(qū)域的拓展。那么，有什么更快拓展的方式呢？由于數(shù)組本身有序…便可以快速拓展紅色 或 藍(lán)色區(qū)域
• 數(shù)組下標(biāo)有效范圍$[0,n?1]$，因此，初始時(shí)l = -1, r = n;
• 循環(huán)的結(jié)束條件是l + 1 != r，因?yàn)閘指向藍(lán)色邊界最右邊，r指向紅色邊界最左邊，當(dāng)l + 1 == r時(shí)整個(gè)數(shù)組已經(jīng)由灰色未知被劃分完畢
• 如果m是紅色區(qū)域，直接r = m；同理…
• 最后結(jié)果返回l還是r要看情況

細(xì)節(jié)1.為什么l的初始值為-1，r的初始值為n

• 假如最終整個(gè)數(shù)組都該是紅色區(qū)域，如果l初始化為0，l一開(kāi)始就處在紅色區(qū)域內(nèi)，這會(huì)造成錯(cuò)誤；同理…

細(xì)節(jié)2.m是否始終處于[0,n)以內(nèi)

• 只有處在這個(gè)區(qū)間以內(nèi)，m才是有意義的
• 先看m的下界，由于m = (l + r) / 2（向下），因此如果我們想讓m盡可能小，就要l和r盡可能小，l的最小值是初始值-1，r如果能進(jìn)入循環(huán)體，最小值是1（不是0），因此m最小值為0
• 再看m上界，同理，r的最大值為n，l如果要進(jìn)入循環(huán)體，最大值為n - 2，因此m最大值為n - 1

細(xì)節(jié)3.更新指針時(shí)，能不能寫(xiě)成l = m + 1或者r = m - 1

• 如果剛好m指向藍(lán)色區(qū)域的最后一個(gè)位置，l如果變?yōu)閙 + 1，就錯(cuò)了；同理…

細(xì)節(jié)4.會(huì)不會(huì)陷入死循環(huán)

• 分別考慮l + 1 == r l + 2 == r l + 3 == r的情況
• l + 1 == r，退出循環(huán)
• l + 2 == r，也就是它們之間隔一個(gè)元素，當(dāng)進(jìn)入循環(huán)體時(shí)，m就是它們之間隔著的那個(gè)元素，接下來(lái)，要么將l設(shè)置成m，要么將r設(shè)置成m，也就是說(shuō)，在循環(huán)體結(jié)束時(shí)，l的下一個(gè)元素一定是r，會(huì)回歸到第一種情況并退出循環(huán)體
• l + 3 == r，會(huì)回歸到第二種情況或者回歸到第一種情況

例子 與 c++庫(kù)函數(shù)

• lower_bound對(duì)應(yīng)大于等于
• upper_bound對(duì)應(yīng)大于

一般流程

• 后處理指的是 例如 只有藍(lán)色區(qū)域/紅色區(qū)域的返回值處理問(wèn)題（需要特判）等

如果沒(méi)有藍(lán)色區(qū)域或者紅色區(qū)域

• 那么l或者r會(huì)不在有效范圍內(nèi)
• 最后結(jié)果特判，l的初始值為-1，r的初始值為n

浮點(diǎn)數(shù)的二分

• 題目 ：通過(guò)二分查找的方式計(jì)算$\sqrt{2}$，要求誤差小于$10^{?6}$
• 退出循環(huán)的條件為r - l <= 1e-8
• 要求誤差小于$10^{?6}$，相當(dāng)于 結(jié)果保留6位小數(shù)；這樣，循環(huán)退出的條件是$10^{?8}$，而輸出則是六位小數(shù)

#include <iostream> #include <iomanip> using namespace std; int main() {double l = -10000, r = 10000;while (r - l > 1e-8){double mid = (l + r) / 2;if (mid * mid >= 2) r = mid;else l = mid;} // printf("%.6lf\n", l);cout << fixed << setprecision(6) << l << endl;return 0; }

總結(jié)

以上是生活随笔為你收集整理的90%的程序员都写错的算法-二分查找万能模版的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。