misha_shik_m2

#include <iostream>
#include <vector>
#include <algorithm>
#include <time.h>
#include <stdlib.h>

using namespace std;

int LS(vector<int> arr, int a) {
    arr.push_back(a);
    int i = 0;
    for (; i < arr.size(); ++i) {
        if (arr[i] == a)
            break;
    }
    return (i == arr.size() - 1) ? -1 : i;
}


ostream& operator<<(ostream& out, vector<int> v) {
    for (int i = 0; i < v.size(); ++i)
        out << v[i] << " ";
    return out;
}

void FastS(vector<int>::iterator begin, vector<int>::iterator end) {
    if (end - begin <= 1)
        return;
    auto left = begin;
    auto right = end - 1;
    auto pivot = begin + (end - begin) / 2;
    while (left < right) {
        while (left < pivot && *left <= *pivot) ++left;
        while (right > pivot && *right >= *pivot) --right;
        if (left < right) {
            if (left == pivot) {
                swap(*left, *right);
                pivot = right;
            }
            else if (right == pivot) {
                swap(*left, *right);
                pivot = left;
            }
            else {
                swap(*left, *right);
            }
        }
        if (left >= right) break;
    }
    FastS(begin, pivot);
    FastS(pivot, end);
}

static int Fibb(vector<int> arr, int elem) {
    int l = 0, r = arr.size() - 1;
    while (r - l > 1) {
        int a = 1, b = 2, c;
        while (l + b - 1 <= r && arr[l + b - 1] < elem) {
            c = a + b;
            a = b;
            b = c;
        }
        l = max(l + a - 1, 0);
        r = min(l + b - 1, int(arr.size() - 1));
    }
    int ret = -1;
    if (arr[l] == elem)
        ret = l;
    else if (arr[r] == elem)
        ret = r;
    return ret;
}


int main(void) {
    setlocale(LC_ALL, "Russian");
    srand(time(NULL));

    int n;
    cout << "Введите длину: ";
    cin >> n;
    vector<int> arr;
    for (int i = 0; i < n; ++i)
        arr.push_back(rand() % 100 - 50);

    cout << arr << endl;
    int a;
    cout << "Введите искомый элемент: ";
    cin >> a;
    cout << "Результат линейного поиска: " << LS(arr, a) << endl;

    FastS(arr.begin(), arr.end());
    cout << arr << endl;
    cin >> a;
    cout << "Результат поиска Фибоначчи: " << Fibb(arr, a) << endl;

    return 0;
}