<style>
html, body, .ui-content {
background: #222222;
color: #00BFFF;
}
::-webkit-scrollbar {
width: 10px;
}
::-webkit-scrollbar-track {
background: transparent;
}
::-webkit-scrollbar-thumb {
background: linear-gradient(180deg, #2BE8CF60 0%, #2B83E860 100%);
border-radius: 3px;
}
::-webkit-scrollbar-thumb:hover {
background: linear-gradient(180deg, #2BE8CF95 0%, #2B83E895 100%);
}
/* 設定 code 模板 */
.markdown-body code,
.markdown-body tt {
background-color: #ffffff36;
}
.markdown-body .highlight pre,
.markdown-body pre {
color: #ddd;
background-color: #00000036;
}
.hljs-tag {
color: #ddd;
}
.token.operator {
background-color: transparent;
}

</style>
###### tags: `Algorithm_Lab`

# Binary Search 結報
## OJ AC截圖
## Code

/*UVa 12097*/
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;

// check this ans is true or false
bool check(double piece, int &friends, vector<int> &pies) {
    if (piece == 0) return true;
    int cnt = 0;
    for (auto &pie : pies)
        cnt += pie / piece;
    return cnt >= friends;
}
// binary search for the ans
double Solve(int &friends, vector<int> &pies, double lowerBound, double upperBound) {
    double left = lowerBound, right = upperBound;
    while (left <= right) {
        double mid = (left + right) / 2;
        if (check(mid, friends, pies))
            left = mid + 0.0001;
        else
            right = mid - 0.0001;
    }
    return left * M_PI;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int Case;
    cin >> Case;
    while (Case--) {
        int pieNum, friends, maxPie = INT_MIN;
        long long sumV = 0;
        cin >> pieNum >> friends;
        vector<int> pies(pieNum);
        for (int i = 0; i < pieNum; ++i) {
            int temp;
            cin >> temp;
            pies[i] = temp * temp;
            sumV += temp * temp;
            maxPie = max(maxPie, temp * temp);
        }
        ++friends;
        cout << fixed << setprecision(4) << Solve(friends, pies, (double)maxPie / friends, (double)sumV / friends) << endl;
    }
}

## 空間複雜度分析

1. 變數：Case, pieNum, i, friends, maxPie, temp, left, right, mid, cnt. total(11)
2. 陣列：pies(n)
total: n + 11 = **O(n)**

## 時間複雜度分析
#### Assume pies' size = n
### Best Case
* 當只輸入一個pie時，upperBound和lowerBound會一樣，一次Solve中的while可找到答案。需跑一次Check函式，而Check函式需尋訪pies(n)
* **O(n)**
### Worst Case
* 共有(upperbound - lowerbound) * 10000種答案，所以Solve函式中的BinarySearch最多需跑lg( (upperbound - lowerbound) * 10000)，而每次的BinarySearch需呼叫一次Check(n)。
* 所以最終需跑n * lg( (所有pie的體積加總 / 所有人 - 最大的pie / 所有人) * 10000) 次
* = n * lg( (upperBound - lowerBound) * 10000)
* = n * lg(upperBound - lowerBound) + 13
* **O(n * lg(upperBound - lowerBound))**

## DATE

2023/03/07