#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 linearSearch(int *arr, int X) {
    for (int i=0; i<sz; i++){
        if (X == arr[i]) return i;
    }
    return -1;
}

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

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

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

    return 0;
}