二分搜尋法的觀念我懶得寫了
這篇筆記主要是當初學習二分搜尋法時
看著那 10 行不到的程式碼，就覺得看一下就會了
結果當要實際寫程式碼時，怎麼寫怎麼錯
因此決定把區間的維護方式記錄在我的筆記中
偽代碼#
根據區間定義不同
程式碼會更動的地方
int binary_search(vector<int> &v, int target) {
int l = 0, r = v.size() - 是否包含;
while (區間是否合法) {
int mid = l + ((r - l) >> 1);
if (v[mid] > target) 縮小右區間;
else if (v[mid] < target) 縮小左區間;
else return mid;
}
return -1;
}
左閉右閉 [l, r]#
初始化
因為左右皆為包含
所以給予正常的索引值即可
int l = 0, r = v.size() - 1;
迴圈條件設定
區間定義為 [l, r] 時，l 和 r 都是合法的
所以當 l == r 時仍然合法
例如：[3, 3]
因此 while 條件要使用 l 小於等於 r
while (l <= r) {
右區間調整
當找到的值大於目標時
表示目標在 mid 的左邊，所以要縮小右區間
因為 mid 已知不是目標，因此 不包含 在區間裡
而區間定義為左閉右閉，也就是 [左包含, 右包含]
所以需要將 mid 減一來避免 mid 放入區間
if (v[mid] > target) r = mid - 1;
左區間調整
同上
所以需要將 mid 加一來避免 mid 放入區間
else if (v[mid] < target) l = mid + 1;
左閉右開 [l, r)#
初始化
因為右不包含，所以需要設定 r 再加 1
int l = 0, r = v.size();
區間定義為 [l, r) 時，r 不在範圍內
所以當 l == r 時區間不合法
因此 while 條件要使用 l 小於 r
迴圈條件調整
while (l < r) {
右區間調整
當找到的值大於目標時
表示目標在 mid 的左邊，所以要縮小右區間
因為 mid 已知不是目標，因此 不包含 在區間裡
而區間定義為左閉右開，也就是 [左包含, 右不包含]
所以 mid 可以直接放入區間
if (v[mid] > target) r = mid;
左區間調整
當找到的值小於目標時
表示目標在 mid 的右邊，所以要縮小左區間
因為 mid 已知不是目標，因此 不包含 在區間裡
而區間定義為左閉右開，也就是 [左包含, 右不包含]
所以需要將 mid 加一來避免 mid 放入區間
else if (v[mid] < target) l = mid + 1;
範例#
左閉右閉
int binary_search(vector<int> &v, int target) {
int l = 0, r = v.size() - 1;
while (l <= r) {
int mid = l + ((r - l) >> 1);
if (v[mid] > target) r = mid - 1;
else if (v[mid] < target) l = mid + 1;
else return mid;
}
return -1;
}
左閉右開
int binary_search(vector<int> &v, int target) {
int l = 0, r = v.size();
while (l < r) {
int mid = l + ((r - l) >> 1);
if (v[mid] > target) r = mid;
else if (v[mid] < target) l = mid + 1;
else return mid;
}
return -1;
}
