#include <iostream>
#include <clocale>
#include <time.h>

using namespace std;


int main()
{
    setlocale(LC_ALL, "Russian");

    const int N = 32; // количество элементов массива arr

    int arr[N]; // объявление массива E с n элементов
    int a, b; // интервалы [a; b]
    int X, L, R, c;
    int average;
    const int iterSize = 10;

    srand(time(0)); // каждый новый запуск, разные значения

    // интервалы [a; b]
    cout << "Введите a:" << endl;
    cin >> a;
    cout << "Введите b:" << endl;
    cin >> b;
    cout << "Поиск значения: "; cin >> X;
    int sum = 0;
    for (int iter = 0; iter < iterSize; iter++)
    {

        for (int i = 0; i < N; i++) {
            arr[i] = a + rand() % (b - a + 1); // числа, сгенерированные  на интервале [a; b]
        }


        // Bubble sort
        int temp;
        for (int i = 0; i < N - 1; i++) {
            for (int j = N - 2; j >= i; j--) {
                if (arr[j] > arr[j + 1]) {
                    // меняем элементы местами
                    temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }

        // Выводим отсортированный массив
        cout << "[Array #" << iter + 1 << "]: ";
        for (int i = 0; i < N; i++)
        {
            cout << arr[i] << " | ";
        }

        int steps = 0;

        L = 0;
        R = N;
        while (L < R - 1)
        {
            steps += 1;

            c = (L + R) / 2;
            if (X < arr[c])
                R = c;
            else if (X == arr[c])
                break;
            else
                L = c;
        }


        std::cout << "Steps: " << steps << std::endl;

        sum += steps;
        //if (arr[L] == X)
        //{
        //    // cout << "A [" << L << "] =" << X << endl;
        //}
        //else
        //    cout << "Не нашли!" << endl;
    }

    average = sum / iterSize;
    std::cout << "Сумма = " << sum << std::endl;
    cout << "Среднее кол-во шагов при бинарном поиске для массива с " << N << " элементов в диапазоне 0 ... 100: " << average << endl;

    return 0;
}