mod2

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

using namespace std;

void print(vector<int> arr) {
    for (int i = 0; i < arr.size(); ++i) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

//Линейный поиск с барьером
int LinS(vector<int> arr, int elem) {
    arr.push_back(elem);
    int i = 0;
    while (arr[i] != elem) ++i;
    arr.pop_back();
    if (i == arr.size())
        return -1;
    else
        return i;
}

//Бинарный поиск
int BinS(vector<int> arr, int elem) {
    int l = 0;
    int r = arr.size();
    while (r - l > 1) {
        int m = (r + l) / 2;
        if (elem < arr[m])
            r = m;
        else
            l = m;
    }
    if (arr[l] == elem) return l;
    else return -1;
}

//Восстановление свойств кучи в поддереве (для пирамидальной сортировки)
void Heapify(vector<int> &arr, int len, int i) {
    int l = 2 * i + 1;
    int r = 2 * i + 2;
    int m = i;
    if (l < len && arr[l] > arr[m])
        m = l;
    if (r < len && arr[r] > arr[m])
        m = r;
    if (m != i) {
        swap(arr[i], arr[m]);
        Heapify(arr, len, m);
    }
}

//Пирамидальная сортировка
void Pyramid(vector<int> &arr) {
    //Построение кучи
    for (int i = arr.size() - 1; i >= 0; --i)
        Heapify(arr, arr.size(), i);
    //Сортировка
    int cnt = arr.size() - 1;
    for (; cnt > 0; --cnt) {
        swap(arr[0], arr[cnt]);
        Heapify(arr, cnt, 0);
    }
}

int main() {
    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);
    }
    cout << "Исходный массив:\n";
    print(arr);
    Pyramid(arr);
    cout << "Отсортированный массив:\n";
    print(arr);
    int e;
    cout << "Введите элемент, который хотите найти>";
    cin >> e;
    cout << "Линейный поиск с барьером: " << LinS(arr, e) << endl;
    cout << "Бинарный поиск: " << BinS(arr, e) << endl;
    return 0;
}