TOJ 55. Number && 二分搜
===
[TOC]
:::warning
本章會用到排序演算法
顧名思義可以把一堆數字從小排到大或從大排到小
本章會用 STL sort 來排序
如果想知道排序實作細節請點[這裡](https://hackmd.io/@arutoria/HyCsjVdYU)
:::
## 二分搜
### 二分搜基本概念

:::info
**二分搜基本概念**
當我們有一個==遞增或遞減==的序列
我們可以藉由猜中間來排除一半的答案
:::

> 例1. 對方在 1~10 裡選一個數字，你必須嘗試猜到它(答案是 7)
> 每次你猜一個答案，他都會告訴你要更大還是更小

我們設答案可能所在的 左界(藍色, 1) 和 右界(紅色, 10)
每次我們都猜左界和右界的中間, 所以猜 (1+10)/2 = 5
答案太小，所以我們把左界移動到 6，因為 1~5 都不可能是答案了

這次中間 = (6+10)/2 = 8
8 太大，因此把右界移到 7。

中間 = (6+7)/2 = 6，把左界移到 7

現在左界 == 右界，裡面只有一個數字，因此答案是 7


### 二分搜實作

實際上我們要搜尋數字可能在序列中是不存在的，或有可能有很多個，因此我們需要 upper_bound 和 lower_bound 的幫忙。
* lower_bound: 搜尋第一個 >= x 的位置
* upper_bound: 搜尋第一個 > x 的位置
以下會教怎麼實作

int arr[9] = {1,2,3,4,5,5,5,8,10}; // 注意 arr 必須排序過

lower_bound 的 code

int lower_bound (int x)
{
    int l = 0, r = 8;
    while (l<r) // 如果左右界指到同一個地方，代表搜到了
    {
        int m = (l+r)/2;
        if (arr[m] < x)
            l = m+1; // 如果 arr[m] < x , 代表 arr[m] 不可能是答案, l = m+1
        else
            r = m; // 但當 arr[m] >= x, arr[m] 還有可能是答案，不能砍到 m
    }
    return l;
}

upper_bound　只有第 7 行不同，連同 arr[m]==x 都要排除掉。

int upper_bound (int x)
{
    int l = 0, r = 8;
    while (l<r)
    {
        int m = (l+r)/2;
        if (arr[m] <= x)
            l = m+1;
        else
            r = m;
    }
}

## TOJ 55. Number
[TOJ 55 題目連結](https://toj.tfcis.org/oj/pro/55/)
> 給你 N 個數字，接下來有 M 筆詢問 x， 請輸出 x 在序列中出現幾次。

讓我們觀察 lower_bound 和 upper_bound 的性質。
當我們對 5 二分搜，可以發現 ==uppper_bound 的位置 - lower_bound 的位置 = 5 的個數==

因此我們可以用這個性質解決 TOJ 55

:::info
STL 有提供 upper_bound 和 lower_bound
語法為
upper_bound(開始指標,結束指標,目標);
他會回傳一個指標, 但如果想要得到整數型別的位置可以這樣寫:

#include <algorithm>
using namespace std;
int arr = {1,2,3,5,5,5,5,5,8};

int main()
{
    int pos = upper_bound(arr,arr+9,5) - arr;
}

***記得要二分搜前要先排序***
:::

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6+10;

int arr[N], n, m;

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

    sort(arr,arr+n);

    cin >> m;
    for (int i=0,x; i<m; i++)
    {
        cin >> x;
        cout << upper_bound(arr,arr+n,x) - lower_bound(arr,arr+n,x) << '\n';
        // 兩個指標相減可以得到位置的差
        // 當元素不存在的時候，兩個函式都會回傳 end(在最後一個元素的下一個), 所以相減還是 0
    }
}