刷 Leetcode 總能遇到關(guān)于二分的題目，但是之前也只是草草地了解一下，每次在使用的時(shí)候都需要找模板，要不然就需要對(duì)于邊界條件進(jìn)行調(diào)試，著實(shí)是很麻煩?。?！
二分介紹：
首先來(lái)簡(jiǎn)單介紹一下二分：二分查找也稱折半查找（Binary Search），它是一種效率較高的查找方法。但是，折半查找要求?線性表?必須采用?順序存儲(chǔ)結(jié)構(gòu)，而且表中元素按關(guān)鍵字有序排列。
優(yōu)點(diǎn)：
- 比較次數(shù)少：二分查找每次將搜索范圍縮小一半，因此比較次數(shù)較少，查找速度快。
- 時(shí)間復(fù)雜度低：在有序數(shù)組中，二分查找的時(shí)間復(fù)雜度為O(log n)，其中n為搜索范圍的大小。相比線性查找的O(n)時(shí)間復(fù)雜度，二分查找更高效。
- 可靠性高：由于二分查找是基于有序數(shù)組進(jìn)行的，因此在數(shù)組有序的前提下，可以保證查找結(jié)果的準(zhǔn)確性。
缺點(diǎn)：
- 要求有序數(shù)組：二分查找要求待查表為有序表，如果數(shù)組無(wú)序，則需要先進(jìn)行排序操作，增加了額外的時(shí)間復(fù)雜度。
- 插入刪除困難：由于二分查找是基于有序數(shù)組進(jìn)行的，插入和刪除操作會(huì)破壞數(shù)組的有序性，因此在插入和刪除元素時(shí)需要維護(hù)數(shù)組的有序性，增加了操作的復(fù)雜度。
在一段有序序列中尋找指定元素（或者該序列中不存在指定元素，返回小于等于指定元素的最大值）等等
二分法講解：
arr數(shù)組為有序序列
left: 左邊界
right:右邊界
mid = (left + right) / 2: 中間下標(biāo)
循環(huán)條件: left .. right
上述為二分中的左邊界（left），右邊界（right），中間元素下標(biāo)（mid）.
二分法分類：
1.閉區(qū)間（左邊界 left = 0, 右邊界 right = arr.size() - 1）（從序列中能夠找到對(duì)應(yīng)的元素）
先插入代碼：
// 1 2 3 5 6 8 9 10（有序數(shù)組中的元素）
int left = 0, right = arr.size() - 1;
int goal = 5;
while(left <= right){
int mid = ( left + right) / 2;
if(goal > arr[mid]){
left = mid + 1;
}else{
right = mid - 1;
}
cout << "Left:" << left << " " << "Right:" << right << " " ;
}
cout << "結(jié)果是" << left << endl;
我們直接進(jìn)行分析（先不要想為什么這樣子，先跟著我的思路走）：
（1）閉區(qū)間初始化：
left = 0, right = arr.size() - 1，則此時(shí) left 和 right 代表的分別是數(shù)組序列的起始元素和末尾元素
（2）循環(huán)條件的設(shè)置：
循環(huán)結(jié)束的標(biāo)志是區(qū)間內(nèi)沒(méi)有元素，因此只有當(dāng) left < right 的時(shí)候才會(huì)終止，因此設(shè)置 while（left <= right）
（3）循環(huán)中 if 語(yǔ)句滿足與不滿足后的 left 和 right 的設(shè)置
暫時(shí)不討論為什么這樣子設(shè)置
來(lái)看終止情況：
終止前的一次： left == right
設(shè) X = left, Y = right (這里的X和Y是不會(huì)變的，因?yàn)榇藭r(shí) left == right，所以可以 X == Y)
此時(shí) mid == X (或者Y)，結(jié)果只有兩種可能，goal對(duì)應(yīng)元素下標(biāo)為 （1）X對(duì)應(yīng)的? 或者 （2）X + 1對(duì)應(yīng)的
前面這句話不理解可以看 while 循環(huán)中的 if 語(yǔ)句，流程圖如下：
?文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-746038.html
接著我們分析兩種情況:
情況一：X對(duì)應(yīng)的元素是目標(biāo)值
則此時(shí)進(jìn)入 if 語(yǔ)句，判斷為 N，進(jìn)入第二個(gè)執(zhí)行語(yǔ)句： right = mid - 1, 則此時(shí) left 不變，結(jié)果就是 left， 就是 X
情況二：X + 1對(duì)應(yīng)的元素是目標(biāo)值
則此時(shí)進(jìn)入 if 語(yǔ)句，判斷為 Y，進(jìn)入第一個(gè)執(zhí)行語(yǔ)句：left = mid + 1，則此時(shí)結(jié)果仍然是 left, 就是 Ｘ + 1
綜上：cout << left << endl; 就可以得到正確答案！
2.閉區(qū)間 從序列中尋找小于等于目標(biāo)值的最大元素
先插入代碼：
// 1 2 3 5 6 8 9 10（有序數(shù)組中的元素） bool flag = true; int left = 0, right = arr.size() - 1, goal = 11; while(left <= right){ int mid = ( left + right) / 2; if(goal > arr[mid]){ left = mid + 1; }else if(goal == arr[mid]){ cout << "找到相等的元素： "<< mid << endl; flag = false; break; }else{ right = mid - 1; } } if(flag) cout << " 小于goal的最大元素下標(biāo)是" << right << endl;
?
分析：首先若是區(qū)間中出現(xiàn)了與 goal 值相等的元素，則直接返回；
這個(gè)是沒(méi)有問(wèn)題的，我們考慮如下情況：其中不存在等于 goal 的元素，則進(jìn)行以下分析：
來(lái)看終止情況：
終止前的一次： left == right
設(shè) X = left, Y = right (這里的X和Y是不會(huì)變的，因?yàn)榇藭r(shí) left == right，所以可以 X == Y)
此時(shí) mid == X (或者Y，因?yàn)閄 == Y)，結(jié)果只有兩種可能，goal對(duì)應(yīng)元素下標(biāo)為 :（1）X對(duì)應(yīng)的? 或者 （2）X - 1對(duì)應(yīng)的
接著我們分析兩種情況:（注意：以下情況考慮的時(shí)候沒(méi)有考慮 goal == arr[mid]，因?yàn)槿羰浅霈F(xiàn)這種情況則直接結(jié)束循環(huán)）
情況一：X對(duì)應(yīng)的元素是目標(biāo)值
則此時(shí)進(jìn)入 if 語(yǔ)句，判斷為 Y，進(jìn)入第一個(gè)執(zhí)行語(yǔ)句： left = mid + 1, 則此時(shí) right 不變，結(jié)果就是 right， 就是 Y (X == Y)
情況二：X - 1對(duì)應(yīng)的元素是目標(biāo)值
則此時(shí)進(jìn)入 if 語(yǔ)句，判斷為 N，進(jìn)入第一個(gè)執(zhí)行語(yǔ)句：right = mid - 1，則此時(shí)結(jié)果是 right, 就是 Y - 1 (Y - 1 == X - 1)
綜上：cout << right << endl; 就可以得到正確答案！
?
?
?
文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-746038.html
到了這里，關(guān)于二分（折半查找）詳細(xì)解答（邊界條件終止條件等等詳細(xì)解釋）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
