fork download
copy 
  1. #include <algorithm>
  2. #include <cstdlib>
  3. #include <ctime>
  4. #include <iostream>
  5. #include <vector>
  6.  
  7. struct node
  8. {
  9.     int data;
  10. };
  11.  
  12. bool operator ==(node const& l, node const& r)
  13. {
  14.     return l.data == r.data;
  15. }
  16.  
  17. bool operator <(node const& l, node const& r)
  18. {
  19.     return l.data < r.data;
  20. }
  21.  
  22. int main()
  23. {
  24.     std::vector<node> v;
  25.     std::srand(std::time(0));
  26.     for (int i = 0; i < 10000; ++i)
  27.     {
  28.         v.push_back({std::rand() % 1000});
  29.     }
  30.  
  31.     node required {444};
  32.  
  33.     // Linear search, requires equality operator...
  34.     auto i = std::find(v.begin(), v.end(), required);
  35.     if (i != v.end())
  36.     {
  37.         std::cout << i->data << " found at index " << i - v.begin() << std::endl;
  38.     }
  39.     else
  40.     {
  41.         std::cout << "Item not found" << std::endl;
  42.     }
  43.  
  44.     // Alternative linear search using a predicate:
  45.     i = std::find_if(v.begin(), v.end(), [](node const& n) { return n.data == 444; } );
  46.     if (i != v.end())
  47.     {
  48.         std::cout << i->data << " found at index " << i - v.begin() << std::endl;
  49.     }
  50.     else
  51.     {
  52.         std::cout << "Item not found" << std::endl;
  53.     }
  54.  
  55.     // Binary search, requires a less-than operator
  56.     // and the container to be sorted...
  57.     std::sort(v.begin(), v.end()); // This is likely to change the index!
  58.     i = std::lower_bound(v.begin(), v.end(), required);
  59.     if (i != v.end() && i->data == required.data)
  60.     {
  61.         std::cout << i->data << " found at index " << i - v.begin() << std::endl;
  62.     }
  63.     else
  64.     {
  65.         std::cout << "Item not found" << std::endl;
  66.     }
  67. }
  68.  
Success #stdin #stdout 0s 2988KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
444 found at index 1618
444 found at index 1618
444 found at index 4427
https://ideone.com/WLXXFg
language:
C++14 (gcc 8.3)
created:
12 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!