#include <cstdlib>
#include <iostream>
#include <ctime>

using namespace std;

const int sz = 10000000;

int arr[sz];
int X, pos;

bool check(int index, int X) {
    if (index <= 0) {
        return arr[index] == X;
    }
    return (arr[index] == X) && (arr[index - 1] != X);
}

int binarySearch(int *arr, int X) {
    int result = -1;
    int l = 0, r = sz - 1;
    int mid;

    while (l <= r) {
        mid = (l + r) / 2;
        if (X <= arr[mid]) {
            if (arr[mid] == X) result = mid;
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }

    return result;
}

int main(){
    for (int i=0; i<sz; i++) arr[i] = i;

    int startTime = time(0);
    for (int t=0; t<10000; t++) {
        X = arr[rand() % sz];
        pos = binarySearch(arr, X);

        if (!check(pos, X)) {
            cout<<"FAILED";
        }
    }
    cout<<"Total time for search: "<<(time(0) - startTime)<<"(s)";

    return 0;
}