#include <iostream>

int main()
{
    const int CAPACITY = 10;

    int array[CAPACITY];

    // реален брой на елементите в масива
    int n;
    do
    {
        std::cout << "n = ";
        std::cin >> n;
    }
    while(n < 1 || n > CAPACITY);

    // извеждане на елементите
    for(int i = 0; i < n; ++i)
    {
        std::cout << "array[" << i << "] = ";
        std::cin >> array[i];
    }

    // добавяне на елемент в сортиран масив
    int x = 0;
    std::cout << x << " will be inserted into the array!\n";

    // имаме ли място?
    if(n + 1 <= CAPACITY)
    {
        int i = 0;
        while(i < n && array[i] < x)
        {
            ++i;
        }

        for(int j = n; j > i; --j)
        {
            array[j] = array[j - 1];
        }

        array[i] = x;
        ++n;
    }

    // изтриване на елемент от масив
    int indexForDel = 2;
    std::cout << "Element at position " << indexForDel << " will be deleted..\n";

    // елементите вдясно от елемнта за изтриване,
    // трябва да бъдат преместени с една позиция надясно
    for(int i = indexForDel; i < n - 1; ++i)
    {
        array[i] = array[i + 1];
    }

    // намаляване на реалния брой елементи
    --n;

    // сортиране по метода на пряката селекция
    for(int i = 0; i < n - 1; ++i)
    {
        int minIndex = i;
        for(int j = i + 1; j < n; ++j)
        {
            if(array[minIndex] > array[j])
            {
                minIndex = j;
            }
        }

        if(i != minIndex)
        {
            int temp = array[i];
            array[i] = array[minIndex];
            array[minIndex] = temp;
        }

    }

    // линейно търсене в сортиран масив

    std::cout << "Search for: ";
    std::cin >> x;

    int i = 0;
    while(i < n && x > array[i])
    {
        ++i;
    }

    if(i < n && x == array[i])
    {
        std::cout << x << " is at position " << i << std::endl;
    }
    else
    {
        std::cout << x << " is NOT in the array!\n";
    }

    // двоично търсене в сортиран масив

    int left = 0, right = n - 1, mid;
    bool found = false;

    while(left <= right && !found)
    {
        mid = (left + right)/2;

        if(array[mid] == x)
        {
            found = true;
        }
        else
        {
            if(x < array[mid])
            {
                right = mid - 1;
            }
            else
            {
                left = mid + 1;
            }
        }
    }

    std::cout << x << " is in the array: " << std::boolalpha << found << std::endl;

    // извеждане на елементите на масива
    for(int i = 0; i < n; ++i)
    {
        std::cout << array[i] << ' ';
    }

    return 0;
}
