# week4 note

## c++ 內建sort
內建sort時間複雜度$O(nlogn)$
sort array

int a[5] = {2, 5, 1, 4, 3};
sort(a, a + 5);

sort vector

vector<int> v = {10, 20, 30, 10, 5};
sort(v.begin(), v.end());

## 二分搜
時間複雜度$O(logn)$
二分搜的寫法很多種
* 聚會講的寫法

    vector<int> v = {1, 4, 6, 7, 8, 12, 200};
    int x = 8;
    
    // 找第一個8>=的位置
    int l = 0, r = v.size() - 1;
    while (l < r) {
        int mid = (l + r) / 2;
        if(v[mid] < x) l = mid + 1;
        else r = mid;
    }
    
    cout << l << endl;

> 如果不知道哪裡錯就印出(cout)l, r看看吧
* 另一個很猛的寫法

    vector<int> v = {1, 4, 6, 7, 8, 12, 200};
    int x = 8;
    int k = 0;
    for (int b = v.size()/2; b >= 1; b /= 2) {
        while (k+b < n && v[k+b] <= x) k += b;
    }
    if (v[k] == x) {
        // x found at index k
    }

> 可以參考[CPH](https://cses.fi/book/book.pdf)裡的binary_search(page 31)
* c++ 內建function

    vector<int> v = {1, 4, 6, 7, 8, 12, 200};
    int x = 8;
    // 第一個 >= x 的位置
    int pos = lower_bound(v.begin(), v.end(), x) - v.begin();
    

* 費事數列程式碼

    #include <bits/stdc++.h>
    using namespace std;

    // f0 = 1, f1 = 1, fn = fn-1+fn-2

    int f(int n) {
        cout << "in: " << n << endl;
        int rt = 0;
        if(n == 0 || n == 1) {
            rt = 1;
        } else {
            rt = f(n-1) + f(n-2);
        }
        cout << "out: " << n << endl;
        return rt;
    }

    int main() {
        cout << f(4) << endl;
    }