How to find out if an item is present in a std::vector in C++?

To determine if an item exists in a std::vector in C++, you can use several methods depending on whether the vector is sorted or unsorted, and whether you need to handle custom data types. Below is a detailed explanation with examples:

1. For Unsorted Vectors: Use std::find

The std::find algorithm (from the <algorithm> header) searches for a value in a range defined by iterators. If the value is found, it returns an iterator pointing to it; otherwise, it returns the end() iterator.

Example with Primitive Types (e.g., int):

#include <iostream>
#include <vector>
#include <algorithm> // Required for std::find

int main() {
    std::vector<int> numbers = {5, 2, 9, 1, 7};
    int target = 9;

    // Use std::find to check existence
    auto it = std::find(numbers.begin(), numbers.end(), target);
    if (it != numbers.end()) {
        std::cout << target << " found in the vector.\n";
    } else {
        std::cout << target << " not found.\n";
    }

    return 0;
}

Example with Custom Objects:

For custom types, ensure the == operator is overloaded:

#include <algorithm>

struct Person {
    std::string name;
    int age;

    // Overload the == operator for std::find to work
    bool operator==(const Person& other) const {
        return (name == other.name) && (age == other.age);
    }
};

int main() {
    std::vector<Person> people = {{"Alice", 30}, {"Bob", 25}};
    Person target = {"Bob", 25};

    auto it = std::find(people.begin(), people.end(), target);
    if (it != people.end()) {
        std::cout << "Person found.\n";
    }

    return 0;
}

2. For Sorted Vectors: Use std::binary_search

If the vector is sorted, std::binary_search (from <algorithm>) provides an efficient O(log n) search. The vector must be sorted in ascending order.

Example:

#include <iostream>
#include <vector>
#include <algorithm> // For std::binary_search and std::sort

int main() {
    std::vector<int> numbers = {1, 2, 5, 7, 9};
    int target = 7;

    // Ensure the vector is sorted (if not already sorted)
    std::sort(numbers.begin(), numbers.end());

    // Check existence with binary search
    bool exists = std::binary_search(numbers.begin(), numbers.end(), target);
    if (exists) {
        std::cout << target << " found.\n";
    }

    return 0;
}

3. Using std::find_if for Custom Comparisons

If you need to search based on a specific property (e.g., a member of a struct), use std::find_if with a lambda or custom predicate.

Example:

#include <algorithm>

struct Product {
    int id;
    std::string name;
};

int main() {
    std::vector<Product> products = {{101, "Apple"}, {202, "Banana"}};
    int targetId = 202;

    // Search by ID using a lambda
    auto it = std::find_if(products.begin(), products.end(),
        [targetId](const Product& p) { return p.id == targetId; });

    if (it != products.end()) {
        std::cout << "Product with ID " << targetId << " found.\n";
    }

    return 0;
}

4. Using std::lower_bound (Advanced)

For sorted vectors, std::lower_bound returns an iterator to the first element not less than the target. You can compare the value to check for equality.

Example:

#include <algorithm>

int main() {
    std::vector<int> sortedVec = {10, 20, 30, 40, 50};
    int target = 30;

    auto it = std::lower_bound(sortedVec.begin(), sortedVec.end(), target);
    if (it != sortedVec.end() && *it == target) {
        std::cout << target << " found.\n";
    }

    return 0;
}

Key Considerations

Method	Time Complexity	Use Case
std::find	O(n)	Unsorted vectors, any data type.
std::binary_search	O(log n)	Sorted vectors (requires sorting).
std::find_if	O(n)	Custom search criteria.
std::lower_bound	O(log n)	Sorted vectors (exact match check).

Edge Cases

• Empty Vector: All methods return false or end().
• Multiple Occurrences: std::find returns the first occurrence; std::binary_search only checks existence.
• Performance: For large unsorted vectors, std::find is slow (linear time). Prefer sorting and using binary search for repeated queries.

Summary

• Use std::find for simple existence checks in unsorted vectors.
• Use std::binary_search for sorted vectors (ensure they are sorted first).
• Use std::find_if for complex conditions or member-based searches.