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