new_lesson8

#include <iostream>

using namespace std;

void genArr(int sz, int arr[]) {
    for (int k = 0; k < sz; k++) {
        arr[k] = rand() % 10000000;
    }
}

void showArr(int sz, int arr[]) {
    for (int k = 0; k < sz; k++)
        cout << arr[k] << " ";
    cout << endl;
}

void selectSort(long sz, int arr[], bool isBiger /* = true*/) {
    long i, j, k;
    int tmp;
    if (isBiger) {
        // перебор по текущим значениям
        for (i = 0; i < sz; i++) {
            k = i;
            tmp = arr[i];
            // поиск минимума
            for (j = i + 1; j < sz; j++) {
                if (arr[j] > tmp) {
                    k = j;
                    tmp = arr[j];
                }
            }
            // обмен текущего значения с минимальным
            if (k != i) {
                arr[k] = arr[i];
                arr[i] = tmp;
            }
        }
    }
    else {
        // перебор по текущим значениям
        for (i = 0; i < sz; i++) {
            k = i;
            tmp = arr[i];
            // поиск минимума
            for (j = i + 1; j < sz; j++) {
                if (arr[j] < tmp) {
                    k = j;
                    tmp = arr[j];
                }
            }
            // обмен текущего значения с минимальным
            if (k != i) {
                arr[k] = arr[i];
                arr[i] = tmp;
            }
        }
    }
}

int Fibonachi(int n) {
    if (n <= 0)
        return 0;
    if (n <= 2)
        return 1;
    return Fibonachi(n - 1) + Fibonachi(n - 2);
}


void quickSort(long sz, int arr[]) {
    int tmp;
    int p = arr[sz / 2];
    int i = 0, j = sz - 1;
    // разбиение на подмассивы
    do {
        while (arr[i] < p) i++;
        while (arr[j] > p) j--;
        if (i <= j) {
            tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
            i++;
            j--;
        }
    } while (i <= j);
    //cout << "terminal: " << p << " | ";
    //showArr(sz, arr);
    // рекурсивный вызов для подмассивов
    if (j > 0) quickSort(j + 1, arr);
    if (i < sz) quickSort(sz - i, arr + i);
}

int binarySearch(int arr[], long sz, int val) {
    int L = 0, R = sz - 1, M;
    while (true) {
        M = (L + R) / 2;
        if (val < arr[M])
            R = M - 1;
        else if (val > arr[M])
            L = M + 1;
        else
            return M;
        if (L > R)
            return -1;
    }
}
void any_task(){
    int n = 0;
    for (int k = 0; k < 3; k++) {
        n = 0;
        while (n < 5) {
            cout << "# ";
            n++;
        }
        cout << endl;
    }
    n = 0;
    while (n < 5) {
        for (int k = 0; k < 3; k++) {
            cout << "A ";
        }
        n++;
        cout << endl;
    }
}

void test_fibo(){
    cout << "Golden: " << 0.5 * (sqrt(5) - 1);
    for (int k = 0; k < 20; ++k) {
        cout << double(Fibonachi(k)) / Fibonachi(k+1) << endl;
    }
    cout << endl;
}

void test_quickSort(){
    const int sz = 100;
    int arr[sz]{11, 17, 4, 10, 29, 4, 18, 18, 22, 14};
    genArr(sz, arr);
    showArr(sz, arr);
    quickSort(sz, arr);
    showArr(sz, arr);

    int pos = binarySearch(arr, sz, 7711);
    cout << pos << " ";
    if (pos >= 0)
        cout << arr[pos];
    else
        cout << "NO";
    cout << endl;
}

int main() {
    test_quickSort();
    //getchar();
    return 0;
}