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


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

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

# 程式碼

#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` 。

## 閉區間

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

## 開區間

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

## 左閉右開區間

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

## 右閉左開區間
最邪教的寫法，~~這樣寫直接踢出去~~。

#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)

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