#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;
}
CiNpbmNsdWRlIDxjc3RkbGliPgojaW5jbHVkZSA8aW9zdHJlYW0+CiNpbmNsdWRlIDxjdGltZT4KCnVzaW5nIG5hbWVzcGFjZSBzdGQ7Cgpjb25zdCBpbnQgc3ogPSAxMDAwMDAwMDsKCmludCBhcnJbc3pdOwppbnQgWCwgcG9zOwoKYm9vbCBjaGVjayhpbnQgaW5kZXgsIGludCBYKSB7CiAgICBpZiAoaW5kZXggPD0gMCkgewogICAgICAgIHJldHVybiBhcnJbaW5kZXhdID09IFg7CiAgICB9CiAgICByZXR1cm4gKGFycltpbmRleF0gPT0gWCkgJiYgKGFycltpbmRleCAtIDFdICE9IFgpOwp9CgppbnQgbGluZWFyU2VhcmNoKGludCAqYXJyLCBpbnQgWCkgewogICAgZm9yIChpbnQgaT0wOyBpPHN6OyBpKyspewogICAgICAgIGlmIChYID09IGFycltpXSkgcmV0dXJuIGk7CiAgICB9CiAgICByZXR1cm4gLTE7Cn0KCmludCBtYWluKCl7CiAgICBmb3IgKGludCBpPTA7IGk8c3o7IGkrKykgYXJyW2ldID0gaTsKCiAgICBpbnQgc3RhcnRUaW1lID0gdGltZSgwKTsKICAgIGZvciAoaW50IHQ9MDsgdDwxMDAwOyB0KyspIHsKICAgICAgICBYID0gYXJyW3JhbmQoKSAlIHN6XTsKICAgICAgICBwb3MgPSBsaW5lYXJTZWFyY2goYXJyLCBYKTsKCiAgICAgICAgaWYgKCFjaGVjayhwb3MsIFgpKSB7CiAgICAgICAgICAgIGNvdXQ8PCJGQUlMRUQiOwogICAgICAgIH0KICAgIH0KICAgIGNvdXQ8PCJUb3RhbCB0aW1lIGZvciBzZWFyY2g6ICI8PCh0aW1lKDApIC0gc3RhcnRUaW1lKTw8IihzKSI7CgogICAgcmV0dXJuIDA7Cn0K