#include <iostream>
#include <ctime>
#include <algorithm>
using namespace std;
double* binary_search8(double* arr, const double& x)
{
if (x<arr[4]) {
if(x<arr[2]) {
if(x<arr[1]) {
return arr;
} else {
return arr + 1;
}
}
else { //2..3
if(x<arr[3]){
return arr + 2;
} else {
return arr + 3;
}
}
} else { // 4..7
if(x<arr[6]) {
if(x<arr[5]) {
return arr + 4;
} else {
return arr + 5;
}
} else { //6..7
if(x<arr[7]) {
return arr + 6;
} else {
return arr + 7;
}
}
}
}
double* binary_search16(double* arr, const double& x)
{
if (x<arr[8]) return binary_search8(arr, x);
else return binary_search8(arr+8, x);
}
int main() {
double test[16] = {0, 10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 110, 120, 130, 140, 150};
vector<double> test_vals;
size_t num_elem = 10000000;
for (size_t i=0; i<num_elem; i++)
test_vals.push_back(rand()%150);
clock_t begin, end;
double elapsed_secs;
// Linear search
double linavg = 0;
begin = clock();
for (size_t i=0; i<num_elem; i++) {
linavg += *(find_if(test, test+16, bind2nd(std::greater_equal<double>(), test_vals[i]))-1);
}
end = clock();
elapsed_secs = double(end - begin) / CLOCKS_PER_SEC;
cout << "linear secs: " <<elapsed_secs << ", testval = " << linavg << std::endl;
// Binary search
double binavg = 0;
begin = clock();
for (size_t i=0; i<num_elem; i++) {
binavg += *binary_search16(test, test_vals[i]);
}
end = clock();
elapsed_secs = double(end - begin) / CLOCKS_PER_SEC;
cout << "binary secs: " <<elapsed_secs << ", testval = " << binavg << std::endl;
// Binary search 2
double binavg2 = 0;
begin = clock();
for (size_t i=0; i<num_elem; i++) {
binavg2 += *(std::upper_bound(test, test+16, test_vals[i])-1);
}
end = clock();
elapsed_secs = double(end - begin) / CLOCKS_PER_SEC;
cout << "binary2 secs: " <<elapsed_secs << ", testval = " << binavg2 << std::endl;
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8Y3RpbWU+CiNpbmNsdWRlIDxhbGdvcml0aG0+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7Cgpkb3VibGUqIGJpbmFyeV9zZWFyY2g4KGRvdWJsZSogYXJyLCBjb25zdCBkb3VibGUmIHgpCnsKICBpZiAoeDxhcnJbNF0pIHsKICAgIGlmKHg8YXJyWzJdKSB7CiAgICAgIGlmKHg8YXJyWzFdKSB7ICAKICAgICAgICByZXR1cm4gYXJyOwogICAgICB9IGVsc2UgewogICAgICAgIHJldHVybiBhcnIgKyAxOwogICAgICB9CiAgICB9CiAgICBlbHNlIHsgLy8yLi4zCiAgICAgIGlmKHg8YXJyWzNdKXsgIAogICAgICAgIHJldHVybiBhcnIgKyAyOwogICAgICB9IGVsc2UgewogICAgICAgIHJldHVybiBhcnIgKyAzOwogICAgICB9CiAgICB9CiAgfSBlbHNlIHsgLy8gNC4uNwogICAgaWYoeDxhcnJbNl0pIHsKICAgICAgaWYoeDxhcnJbNV0pIHsgIAogICAgICAgIHJldHVybiBhcnIgKyA0OwogICAgICB9IGVsc2UgewogICAgICAgIHJldHVybiBhcnIgKyA1OwogICAgICB9CiAgICB9IGVsc2UgeyAvLzYuLjcKICAgICAgaWYoeDxhcnJbN10pIHsgIAogICAgICAgIHJldHVybiBhcnIgKyA2OwogICAgICB9IGVsc2UgewogICAgICAgIHJldHVybiBhcnIgKyA3OwogICAgICB9CiAgICB9CiAgfQp9CgoKZG91YmxlKiBiaW5hcnlfc2VhcmNoMTYoZG91YmxlKiBhcnIsIGNvbnN0IGRvdWJsZSYgeCkKewoJaWYgKHg8YXJyWzhdKSByZXR1cm4gYmluYXJ5X3NlYXJjaDgoYXJyLCB4KTsKCWVsc2UgcmV0dXJuIGJpbmFyeV9zZWFyY2g4KGFycis4LCB4KTsKfQoKaW50IG1haW4oKSB7CmRvdWJsZSB0ZXN0WzE2XSA9IHswLCAxMCwgMjAsIDMwLCA0MCwgNTAsIDYwLCA3MCwgODAsIDkwLCAxMDAsIDExMCwgMTIwLCAxMzAsIDE0MCwgMTUwfTsKCiAgdmVjdG9yPGRvdWJsZT4gdGVzdF92YWxzOwogIHNpemVfdCBudW1fZWxlbSA9IDEwMDAwMDAwOwogIGZvciAoc2l6ZV90IGk9MDsgaTxudW1fZWxlbTsgaSsrKQogICAgdGVzdF92YWxzLnB1c2hfYmFjayhyYW5kKCklMTUwKTsKCiAgY2xvY2tfdCBiZWdpbiwgZW5kOwogIGRvdWJsZSBlbGFwc2VkX3NlY3M7CgogIC8vIExpbmVhciBzZWFyY2gKICBkb3VibGUgbGluYXZnID0gMDsKICBiZWdpbiA9IGNsb2NrKCk7CiAgZm9yIChzaXplX3QgaT0wOyBpPG51bV9lbGVtOyBpKyspIHsgICAKICAgIGxpbmF2ZyArPSAqKGZpbmRfaWYodGVzdCwgdGVzdCsxNiwgYmluZDJuZChzdGQ6OmdyZWF0ZXJfZXF1YWw8ZG91YmxlPigpLCB0ZXN0X3ZhbHNbaV0pKS0xKTsKICB9CiAgZW5kID0gY2xvY2soKTsKICBlbGFwc2VkX3NlY3MgPSBkb3VibGUoZW5kIC0gYmVnaW4pIC8gQ0xPQ0tTX1BFUl9TRUM7CiAgY291dCA8PCAibGluZWFyIHNlY3M6ICIgPDxlbGFwc2VkX3NlY3MgPDwgIiwgdGVzdHZhbCA9ICIgPDwgbGluYXZnIDw8IHN0ZDo6ZW5kbDsKCgogIC8vIEJpbmFyeSBzZWFyY2gKICBkb3VibGUgYmluYXZnID0gMDsKICBiZWdpbiA9IGNsb2NrKCk7CiAgZm9yIChzaXplX3QgaT0wOyBpPG51bV9lbGVtOyBpKyspIHsKICAgIGJpbmF2ZyArPSAqYmluYXJ5X3NlYXJjaDE2KHRlc3QsIHRlc3RfdmFsc1tpXSk7CiAgfQogIGVuZCA9IGNsb2NrKCk7CiAgZWxhcHNlZF9zZWNzID0gZG91YmxlKGVuZCAtIGJlZ2luKSAvIENMT0NLU19QRVJfU0VDOwogIGNvdXQgPDwgImJpbmFyeSBzZWNzOiAiIDw8ZWxhcHNlZF9zZWNzIDw8ICIsIHRlc3R2YWwgPSAiIDw8IGJpbmF2ZyA8PCBzdGQ6OmVuZGw7CgogIC8vIEJpbmFyeSBzZWFyY2ggMgogIGRvdWJsZSBiaW5hdmcyID0gMDsKICBiZWdpbiA9IGNsb2NrKCk7CiAgZm9yIChzaXplX3QgaT0wOyBpPG51bV9lbGVtOyBpKyspIHsKICAgIGJpbmF2ZzIgKz0gKihzdGQ6OnVwcGVyX2JvdW5kKHRlc3QsIHRlc3QrMTYsIHRlc3RfdmFsc1tpXSktMSk7CiAgfQogIGVuZCA9IGNsb2NrKCk7CiAgZWxhcHNlZF9zZWNzID0gZG91YmxlKGVuZCAtIGJlZ2luKSAvIENMT0NLU19QRVJfU0VDOwogIGNvdXQgPDwgImJpbmFyeTIgc2VjczogIiA8PGVsYXBzZWRfc2VjcyA8PCAiLCB0ZXN0dmFsID0gIiA8PCBiaW5hdmcyIDw8IHN0ZDo6ZW5kbDsKICAKICByZXR1cm4gMDsKfQ==