Binary-Search

二分搜尋法的觀念我懶得寫了
這篇筆記主要是當初學習二分搜尋法時
看著那 10 行不到的程式碼，就覺得看一下就會了
結果當要實際寫程式碼時，怎麼寫怎麼錯
因此決定把區間的維護方式記錄在我的筆記中

偽代碼

根據區間定義不同
程式碼會更動的地方

1
2
3
4
5
6
7
8
9
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]

初始化

因為左右皆為包含
所以給予正常的索引值即可

1

int l = 0, r = v.size() - 1;

迴圈條件設定

區間定義為 [l, r] 時，l 和 r 都是合法的
所以當 l == r 時仍然合法
例如：[3, 3]
因此 while 條件要使用 l 小於等於 r

1

while (l <= r) {

右區間調整

當找到的值大於目標時
表示目標在 mid 的左邊，所以要縮小右區間
因為 mid 已知不是目標，因此 不包含 在區間裡
而區間定義為左閉右閉，也就是 [左包含, 右包含]
所以需要將 mid 減一來避免 mid 放入區間

1

if (v[mid] > target) r = mid - 1;

左區間調整

同上
所以需要將 mid 加一來避免 mid 放入區間

1

else if (v[mid] < target) l = mid + 1;

左閉右開 [l, r)

初始化

因為右不包含，所以需要設定 r 再加 1

1

int l = 0, r = v.size();

區間定義為 [l, r) 時，r 不在範圍內
所以當 l == r 時區間不合法
因此 while 條件要使用 l 小於 r

迴圈條件調整

1

while (l < r) {

右區間調整

當找到的值大於目標時
表示目標在 mid 的左邊，所以要縮小右區間
因為 mid 已知不是目標，因此 不包含 在區間裡
而區間定義為左閉右開，也就是 [左包含, 右不包含]
所以 mid 可以直接放入區間

1

if (v[mid] > target) r = mid;

左區間調整

當找到的值小於目標時
表示目標在 mid 的右邊，所以要縮小左區間
因為 mid 已知不是目標，因此 不包含 在區間裡
而區間定義為左閉右開，也就是 [左包含, 右不包含]
所以需要將 mid 加一來避免 mid 放入區間

1

else if (v[mid] < target) l = mid + 1;

範例

左閉右閉

1
2
3
4
5
6
7
8
9
10

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;
}

左閉右開

1
2
3
4
5
6
7
8
9
10

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;
}