#include <iostream>

using namespace std;

int binary_search(int* arr, int x, int left, int right) {

    if (left >= right) {
        return -1;
    }

    int mid = (left + right) / 2;

    if (arr[mid] == x) {
        return mid;
    }
    else if (arr[mid] > x) {
        return binary_search(arr, x, left, mid);
    }
    else {
        return binary_search(arr, x, mid + 1, right);
    }
}


// функция линейного поиска для сравнения
int search(int* arr, int size, int x) {
    for (int i = 0; i < size; i++) {
        if (arr[i] == x) {
            return i;
        }
    }
    return -1;
}

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

    const int size = 200000;

    int arr[size];

    for (int i = 0; i < size; i++) {
        arr[i] = i;
    }

    int index, x = 153879;

    int start_time = clock();

    for (int i = 0; i < 100000; i++) {
        index = binary_search(arr, x, 0, size);
    }

    int end_time = clock();

    cout << "index " << index << ", time " << end_time - start_time << " milliseconds" << endl;

    start_time = clock();

    for (int i = 0; i < 100000; i++) {
        index = search(arr, size, x);
    }

    end_time = clock();

    cout << "index " << index << ", time " << end_time - start_time << " milliseconds" << endl;

}