using namespace std;

#include <iostream>
#include <vector>


int binarySearch(std::vector<int>& arr, int x, int left, int right) {
    if (right <= left) {
        // промежуток пуст
        return -1;
    }
    // промежуток не пуст
    int mid = (left + right) / 2;
    if (arr[mid] == x) {
        // центральный элемент — искомый
        return mid;
    }
    else if (x < arr[mid]) {
        // искомый элемент меньше центрального значит следует искать в левой половине
        return binarySearch(arr, x, left, mid);
    }
    else {
        // иначе следует искать в правой половине
        return binarySearch(arr, x, mid + 1, right);
    }
}

int binarySearch2(std::vector<int>& arr, int x, int left, int right) {
    if (right <= left) {
        // промежуток пуст
        return -1;
    }
    // промежуток не пуст
    int mid = (left + right) / 2;
    if (arr[mid] == x) {
        // центральный элемент — искомый
        return mid;
    }
    return  x < arr[mid] ? binarySearch2(arr, x, left, mid) : binarySearch2(arr, x, mid + 1, right);
}

int binarySearch3(std::vector<int>& arr, int x, int left, int right) {
    if (right <= left) {
        // промежуток пуст
        return -1;
    }
    // промежуток не пуст
    int mid = (left + right) / 2;
    if (arr[mid] == x) {
        // центральный элемент — искомый
        return mid;
    }
    if (x < arr[mid]) {
        // искомый элемент меньше центрального значит следует искать в левой половине
        return binarySearch3(arr, x, left, mid);
    }
    if (x > arr[mid]) {
        // иначе следует искать в правой половине
        return binarySearch3(arr, x, mid + 1, right);
    }
}

int main() {
    vector<int> arr(1000000);

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

    int index, x = 999999;

    int start_time = clock();

    for (int i = 0; i < 1000000; i++) {
        index = binarySearch(arr, x, 0, arr.size());
    }

    int end_time = clock();

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

    start_time = clock();

    for (int i = 0; i < 1000000; i++) {
        index = binarySearch2(arr, x, 0, arr.size());
    }

    end_time = clock();

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

    start_time = clock();

    for (int i = 0; i < 1000000; i++) {
        index = binarySearch3(arr, x, 0, arr.size());
    }

    end_time = clock();

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