【二分查找的核心思想】● 二分查找的核心只圍繞一個關(guān)鍵問題展開完成 mid 位置的條件判斷之后目標(biāo)答案究竟存在于左半?yún)^(qū)間還是右半?yún)^(qū)間。對該問題的不同判定結(jié)論直接決定了區(qū)間邊界的修改邏輯從而衍生出各式各樣的代碼模板但萬變不離其宗?！?不失一般性在二分查找中我們使用循環(huán)條件 while(leftright)并統(tǒng)一采用“左閉右開區(qū)間 [left, right)”的模型。在該模型下空區(qū)間對應(yīng) left rightleft 指向的元素在搜索范圍內(nèi)right 指向的元素不在搜索范圍內(nèi)這是后續(xù)所有邏輯推導(dǎo)的基礎(chǔ)?！?“左閉右開區(qū)間 [left, right)”二分模型的推薦代碼1查找第一個 x 的數(shù)本代碼為什么是找第一個 ≥x 的數(shù)而不是第一個 x 的數(shù)原因在于區(qū)間收縮的方向。/* The index starts from 0, with the range [0,n), call ffir(0,n,x) */ int ffir(int le,int ri,int x) { //find first x while(leri) { int midleri1; if(q[mid]x) lemid1; else rimid; } return le; }2查找最后一個 x 的數(shù)/* The index starts from 0, with the range [0,n), call ffir(0,n,x) */ int flas(int le,int ri,int x) { //find last x //Find the position of the first occurrence that x while(leri) { int midleri1; if(q[mid]x) rimid; else lemid1; } return le-1; //The position before the first occurrence of x is the last position of x }●“左閉右開區(qū)間 [left, right)” 的二分模型中right 永遠(yuǎn)指向第一個不在范圍內(nèi)的位置。所以基于此模型對于長度為 n 的數(shù)組對外調(diào)用形式為ffir(0, n, x)。即初始傳入邊界為 left0、rightn建立的初始搜索區(qū)間 [0,n)參數(shù) x 是待查找的目標(biāo)。?1當(dāng) q[mid] x 時mid 及其左邊全部排除往右走 → le mid 1。2當(dāng) q[mid] ≥ x 時mid 可能是答案但左邊可能還有更早的 ≥ x 的數(shù)往左收 → ri mid。最終 left 停在哪里?停在第一個使 q[mid] ≥ x 成立的位置?！?二分中的謂詞函數(shù)就是用來判斷 mid 位置對應(yīng)的值是否滿足某種條件的那個函數(shù)。在二分代碼里謂詞函數(shù)通常命名為 check(mid) 或直接寫在 if 條件中其作用只有一個判斷 mid 位置是否滿足某一條件據(jù)此決定下一步向哪一側(cè)收縮搜索范圍。●謂詞函數(shù)是二分的靈魂必須先定義再進行二分編碼。不事先約定清楚你根本不知道二分返回的是什么。同樣一個數(shù)組、同樣一個目標(biāo)值謂詞函數(shù)從改成答案就可能截然不同。因此寫二分的第一步永遠(yuǎn)是定義謂詞函數(shù)?！白箝]右開區(qū)間 [left, right)” 的二分模型中謂詞約定如下1check(mid) true 代表下標(biāo)為 mid 的元素滿足目標(biāo)性質(zhì)答案下標(biāo)一定不大于 mid即答案可以是 mid 本身也可以出現(xiàn)在 mid 左側(cè)。2check(mid) false 代表下標(biāo)為 mid 的元素不滿足目標(biāo)性質(zhì)并且下標(biāo)小于等于 mid 的所有元素也都不可能是答案答案只能出現(xiàn)在 mid 右側(cè)。●謂詞約定就是明確聲明“二分中的 check(mid) 函數(shù)返回 true 或 false 分別代表什么含義以及這個返回值如何指導(dǎo)下一步的區(qū)間收縮”。謂詞約定是二分的“設(shè)計文檔”沒有它代碼就是一串沒有意義的符號?！緮?shù)組與調(diào)用方式】數(shù)據(jù)數(shù)組 q [1, 3, 5, 7, 9]長度 n 5有效下標(biāo) 0, 1, 2, 3, 4。調(diào)用ffir(0, 5, 6)? → 區(qū)間 [0, 5)包含下標(biāo) 0,1,2,3,4正好是全部元素。目標(biāo)找第一個 ≥ 6? 的位置。1第一輪mid (05)/2 2整數(shù)除法下取整q[2] 5 6 → check 為假。5 6不可能是答案且它左邊的所有數(shù)下標(biāo)0,1也都小于6全部扔掉。更新left mid 1 3把 mid 踢出去right 不變還是5。此時區(qū)間 [3, 5) 包含下標(biāo) 3, 4。2第二輪mid (35)/2 4q[4] 9 ≥ 6 → check 為真。9 ≥ 6可能是答案但左邊可能還有更小的滿足條件的數(shù)比如下標(biāo)為 3 的數(shù)值 7。更新right mid 4把搜索上限拉到 mid 位置left 不變還是 3。此時區(qū)間 [3, 4) 只包含下標(biāo)3。3第三輪mid (34)/2 3q[3] 7 ≥ 6 → check 為真。7 ≥ 6滿足條件但左邊已經(jīng)沒有元素了區(qū)間只剩這一個。更新right mid 3此時 left 3right 3left right循環(huán)結(jié)束。返回 left 3即第一個 ≥ 6 的數(shù)的下標(biāo)是 3對應(yīng)數(shù)值 7?！舅惴ùa】→ https://www.luogu.com.cn/problem/U383691#include bits/stdc.h using namespace std; const int maxn1e55; int q[maxn]; int ffir(int le,int ri,int x) { //find first while(leri) { int midleri1; if(q[mid]x) rimid; else lemid1; } return le; } int flas(int le,int ri,int x) { //find last while(leri) { int midleri1; if(q[mid]x) rimid; else lemid1; } return le-1; } int main() { int n,m; scanf(%d%d,n,m); for(int i0; in; i) scanf(%d,q[i]); while(m--) { int x; scanf(%d,x); int leffir(0,n,x); if(q[le]!x) cout-1 -1endl; else { coutle ; coutflas(0,n,x)endl; } } return 0; } /* in: 6 3 1 2 2 3 3 4 3 4 5 out: 3 4 5 5 -1 -1 */【參考文獻】https://blog.csdn.net/hnjzsyjyj/article/details/148748529