m_mod_2

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

using namespace std;

void print(vector<int> v) {
    for (int i = 0; i < v.size(); ++i)
        cout << v[i] << " ";
    cout << endl;
}

int LinearSearch(vector<int> v, int elem) {
    v.push_back(elem);
    int i = 0;
    while (v[i] != elem) i++;
    return (i == v.size() - 1) ? -1 : i;
}

void Heapify(vector<int>&v, int n, int a) {
    int l = a * 2 + 1;
    int r = a * 2 + 2;
    int m = a;
    if (l < n && v[l] > v[m]) m = l;
    if (r < n && v[r] > v[m]) m = r;
    if (m != a) {
        swap(v[m], v[a]);
        Heapify(v, n, m);
    }
}

vector<int> PyramidSort(vector<int> v) {
    for (int i = v.size() - 1; i >= 0; --i) {
        Heapify(v, v.size(), i);
    }
    int r = v.size() - 1;
    for (; r > 0; --r) {
        Heapify(v, r + 1, 0);
        swap(v[0], v[r]);
    }
    return v;
}

int InterpolationSearch(vector<int> v, int key) {
    int m = 0, l = 0, r = v.size() - 1;
    while (v[l] <= key && v[r] >= key) {
        m = l + ((key - v[l]) * (r - l)) / (v[r] - v[l]);
        if (v[m] < key) l = m + 1;
        else if (v[m] > key) r = m - 1;
        else return m;
    }
    return (v[l] == key) ? l : -1;

}

int main(void) {
    time_t t = time(NULL);
    cout << "t = " << t << endl;
    srand(t);

    int n, e;
    cout << "Length>";
    cin >> n;
    vector<int> v;
    for (int i = 0; i < n; ++i) v.push_back(rand() % 100 - 50);
    print(v);
    cout << "Element>";
    cin >> e;
    cout << LinearSearch(v, e) << endl << endl;
    v = PyramidSort(v);
    print(v);
    cout << "Element>";
    cin >> e;
    cout << InterpolationSearch(v, e) << endl;
    return 0;
}