/** * I've setted low numbers to prevent SL * returning back a Time Limit Exceeded, * real advantages can be seen in an offline * compiler with very large numbers. * * Note: * There are cases in which a * simple sequential search can be much more * efficient than a binary search, use them * properly and search for online resources * to learn more about these two popular * algorithms. */ #include #include #include #include #include #include template std::vector search(T v, void(*search_method)(T v)) { auto start = std::chrono::high_resolution_clock::now(); for(int i = 0; i < 1000; i++) search_method(v); auto end = std::chrono::high_resolution_clock::now(); return std::vector { (int)(std::chrono::duration_cast(end-start)).count(), (int)(std::chrono::duration_cast(end-start)).count() };; } template void sequential_search(T v) { std::find(v.begin(), v.end(), rand()%999+1); } template void binary_search(T v) { std::lower_bound(v.begin(), v.end(), rand()%999+1); } int main(void) { srand(time(0)); // Generate a vector with 100 pseudo-random elements std::vector v; v.reserve(100); for(int i = 0; i < 100000; i++) v.push_back(rand()%999+1); // Sort vector std::sort(v.begin(), v.end()); // Sequantial search std::vector tot = search(v, sequential_search); std::cout << "Sequential search: " << tot.at(0) << "ms which are equivalent to " << tot.at(1) << "s"; // Binary search tot = search(v, binary_search); std::cout << "\nBinary search: " << tot.at(0) << "ms which are equivalent to " << tot.at(1) << "s"; return 0; }

Sequential VS Binary | Performance comparison