??該視頻首發公眾號和B站，目前試看版本為B站版本，主要講解二分查找的通用模板，文章末尾有相應的原始碼，
<iframe id="CsA38MVZ-1634776231564" src="https://player.bilibili.com/player.html?aid=336145464" allowfullscreen="true" data-mediaembed="bilibili"></iframe>
int binarySearch(int *arr, int arrSize, int x) {
int l = -1, r = arrSize; // (1)
int mid;
while(r - l > 1) { // (2)
mid = l + (r - l) / 2; // (3)
if( isGreen(arr[mid], x) ) // (4)
r = mid; // (5)
else
l = mid; // (6)
}
return r; // (7)
}
- ( 1 ) (1) (1) l l l 代表 紅色游標， r r r 代表 綠色游標；
- ( 2 ) (2) (2) 當區間長度大于 2 的時候，二分縮小區間，這一步被稱為 區間收斂；
- ( 3 ) (3) (3) m i d mid mid 為計算出來的區間 [ l , r ] [l, r] [l,r] 的中點；
- ( 4 ) (4) (4) 判斷區間中點對應的元素是 綠色 還是 紅色；
- ( 5 ) (5) (5) 如果 中點元素 是 綠色，則從 中點 到 r r r 的值都為 綠色，用 中點 替換 綠色游標；
- ( 6 ) (6) (6) 如果 中點元素 是 紅色，則從 l l l 到 中點 的值都為 紅色，用 中點 替換 紅色游標；
- ( 7 ) (7) (7) 這個地方是模板需要變通的地方，如果需要回傳紅色邊界，那么應該回傳 l l l；反之，如果需要回傳綠色邊界，則應該回傳 r r r，這個問題中，是后者，
??
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/330455.html
標籤：其他
下一篇：關于CSP2021