---
# System prepended metadata

title: binary search  二分搜尋法
tags: [程設班講義]

---

# 簡介
二分搜尋法簡稱二分搜，如同字面意思，二分，把東西分成兩部分，接著在搜尋。

![image](https://hackmd.io/_uploads/ByF_r1qmxx.png)

相信有在思考的人一定有發現一個問題，我陣列的資料是照順序排列的。

:::warning
所以在用二分搜前要先讓陣列裡的資料排序過。
:::

# 程式碼
```cpp=
#include <bits/stdc++.h>
using namespace std ;

int main() {
    int n ;
    cin >> n ;
    int arr[n] ;

    for (int i = 0 ; i < n ; i++) {
        cin >> arr[i] ;
    }

    sort (arr, arr + n) ;

    int target;
    while (cin >> target) {
        int left = 0 , right = n ;
        bool found = false ;

        while (left < right) {
            int mid = left + (right - left) / 2 ;

            if (arr[mid] > target) {
                right = mid ;
            } 
            else if (arr[mid] < target) {
                left = mid + 1 ; 
            } 
            else {
                cout << mid + 1 << endl ;  
                found = true ;
                break ;
            }
        }

        if (!found) {
            cout << "not found" << endl ;
        }
    }

    return 0 ;
}
```

# 區間
###### 既然都提了二分搜，當然要開啟宗教戰爭阿。

## 前情提要
`[a , b]` 代表閉區間，包含 `a , b` 。

`(a , b)` 代表開區間，不包含 `a , b` 。

`[a , b)` 代表左閉右開區間，包含 `1` ，不包含 `6` 。

`(a , b]` 代表右閉左開區間，不包含 `1` ，包含 `6` 。

## 閉區間
```cpp=
#include <bits/stdc++.h>
using namespace std ;

int main() {
    int n ;
    cin >> n ;
    int arr[n] ;

    for (int i = 0 ; i < n ; i++) {
        cin >> arr[i] ;
    }

    sort (arr, arr + n) ;

    int target;
    while (cin >> target) {
        int left = 0 , right = n - 1;
        bool found = false ;

        while (left <= right) {
            int mid = left + (right - left) / 2 ;

            if (arr[mid] > target) {
                right = mid - 1;
            } 
            else if (arr[mid] < target) {
                left = mid + 1 ; 
            } 
            else {
                cout << mid + 1 << endl ;  
                found = true ;
                break ;
            }
        }

        if (!found) {
            cout << "not found" << endl ;
        }
    }

    return 0 ;
}
```

## 開區間
```cpp=
#include <bits/stdc++.h>
using namespace std ;

int main() {
    int n ;
    cin >> n ;
    int arr[n] ;

    for (int i = 0 ; i < n ; i++) {
        cin >> arr[i] ;
    }

    sort (arr, arr + n) ;

    int target;
    while (cin >> target) {
        int left = -1 , right = n ;
        bool found = false ;

        while (left < right) {
            int mid = left + (right - left) / 2 ;

            if (arr[mid] > target) {
                right = mid ;
            } 
            else if (arr[mid] < target) {
                left = mid ; 
            } 
            else {
                cout << mid + 1 << endl ;  
                found = true ;
                break ;
            }
        }

        if (!found) {
            cout << "not found" << endl ;
        }
    }

    return 0 ;
}
```

## 左閉右開區間
```cpp=
#include <bits/stdc++.h>
using namespace std ;

int main() {
    int n ;
    cin >> n ;
    int arr[n] ;

    for (int i = 0 ; i < n ; i++) {
        cin >> arr[i] ;
    }

    sort (arr, arr + n) ;

    int target;
    while (cin >> target) {
        int left = 0 , right = n ;
        bool found = false ;

        while (left < right) {
            int mid = left + (right - left) / 2 ;

            if (arr[mid] > target) {
                right = mid ;
            } 
            else if (arr[mid] < target) {
                left = mid + 1 ; 
            } 
            else {
                cout << mid + 1 << endl ;  
                found = true ;
                break ;
            }
        }

        if (!found) {
            cout << "not found" << endl ;
        }
    }

    return 0 ;
}
```

## 右閉左開區間
最邪教的寫法，~~這樣寫直接踢出去~~。
```cpp=
#include <bits/stdc++.h>
using namespace std ;

int main() {
    int n ;
    cin >> n ;
    int arr[n] ;

    for (int i = 0 ; i < n ; i++) {
        cin >> arr[i] ;
    }

    sort (arr, arr + n) ;

    int target;
    while (cin >> target) {
        int left = -1 , right = n - 1;
        bool found = false ;

        while (left <= right) {
            int mid = left + (right - left) / 2 ;

            if (arr[mid] > target) {
                right = mid - 1;
            } 
            else if (arr[mid] < target) {
                left = mid ; 
            } 
            else {
                cout << mid + 1 << endl ;  
                found = true ;
                break ;
            }
        }

        if (!found) {
            cout << "not found" << endl ;
        }
    }

    return 0 ;
}
```

## 總結
| 方法 | 初始區間 | while 條件 | right 更新 | left 更新 |
| -------- | -------- | -------- | -------- | -------- |
| 閉區間 `[left, right]`    |  `[0, n-1] `     |  `left <= right`  |  `right = mid - 1`  |`left = mid + 1`   |
| 開區間 `(left, right)`  | `(-1, n)`     | `left < right`     |`right = mid`     |`left = mid`     |
| 左閉右開 `[left, right)`     | `[0, n)`     | `left < right`     |`right = mid`     |`left = mid + 1`     |
| 右閉左開 `(left, right]`     | `(-1, n-1]`     | `left <= right`     |`right = mid - 1`     |`left = mid`     |

# 例題
[a065: Sort! Sort! Sort! And Search! Search! Search!](https://dandanjudge.fdhs.tyc.edu.tw/ShowProblem?problemid=a065)

[a702: D. 追番科高校的劣等生](https://dandanjudge.fdhs.tyc.edu.tw/ShowProblem?problemid=a702)

[a710: D. 簡單的陣列問題](https://dandanjudge.fdhs.tyc.edu.tw/ShowProblem?problemid=a710)

[b145: 離散化](https://dandanjudge.fdhs.tyc.edu.tw/ShowProblem?problemid=b145)



###### 都看到這了難道不按個愛心支持一下嗎?