#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <vector>

struct node
{
    int data;
};

bool operator ==(node const& l, node const& r)
{
    return l.data == r.data;
}

bool operator <(node const& l, node const& r)
{
    return l.data < r.data;
}

int main()
{
    std::vector<node> v;
    std::srand(std::time(0));
    for (int i = 0; i < 10000; ++i)
    {
        v.push_back({std::rand() % 1000});
    }

    node required {444};

    // Linear search, requires equality operator...
    auto i = std::find(v.begin(), v.end(), required);
    if (i != v.end())
    {
        std::cout << i->data << " found at index " << i - v.begin() << std::endl;
    }
    else
    {
        std::cout << "Item not found" << std::endl;
    }
    
    // Alternative linear search using a predicate:
    i = std::find_if(v.begin(), v.end(), [](node const& n) { return n.data == 444; } );
    if (i != v.end())
    {
        std::cout << i->data << " found at index " << i - v.begin() << std::endl;
    }
    else
    {
        std::cout << "Item not found" << std::endl;
    }

    // Binary search, requires a less-than operator
    // and the container to be sorted...
    std::sort(v.begin(), v.end()); // This is likely to change the index!
    i = std::lower_bound(v.begin(), v.end(), required);
    if (i != v.end() && i->data == required.data)
    {
        std::cout << i->data << " found at index " << i - v.begin() << std::endl;
    }
    else
    {
        std::cout << "Item not found" << std::endl;
    }
}