Start learning free

LESSON 131 OF 409 · LOOPS & CONDITIONALS

Array Contains in C++: Linear Search with a Range-Based Loop

Practice Read the full explanation

Given an array of integers nums and another integer value, check if value occurs in nums.

If the value occurs in nums, return true; otherwise return false.


Examples:

contains([1, 2, 4, 5], 4) -> true

contains([-1, 2, -4, 0, 10], 7) -> false

Note:

Do not use builtin functions such as find() or includes(), it would defy the purpose of the challenge. Write the whole code yourself.

STEP 1 OF 3
    Ctrl + Enter to check

    C++ · LOOPS & CONDITIONALS

    Array Contains in C++, explained

    Problem overview

    The method contains receives a vector<int> called nums and an int called value. It returns true if value appears anywhere in nums and false otherwise. The statement asks you to write the search yourself instead of calling a library function such as find().

    For nums = [1, 2, 4, 5] and value = 4 the answer is true, because 4 is the third element. For nums = [-1, 2, -4, 0, 10] and value = 7 the answer is false: none of the five elements equals 7.

    Approach: look at the elements one by one

    Nothing is known about the order of the numbers, so there is no shortcut. The only way to be sure a value is missing is to look at every element. The method therefore walks through the vector from the first element to the last, compares each element with value, and stops as soon as it finds a match. This is called a linear search.

    Two outcomes are possible:

    • The loop finds an element equal to value. The answer is known, so the method returns true immediately and skips the rest of the vector.
    • The loop reaches the end without a match. Only then can the method answer false.

    The false answer has to wait until after the loop. A common slip is to put return false inside the loop, in an else branch. That would give up after comparing only the first element.

    Step by step

    1. Loop over the vector with a range-based for. The loop for (int val : nums) gives you each element in turn, in the variable val, without an index. You do not need positions here, only values.
    2. Compare each element with value. If val == value, return true. Returning from inside the loop ends the whole method, so the remaining elements are never visited.
    3. Return false after the loop. The only way to reach that line is to finish the loop without a match. No else is needed.

    The solution in C++

    class Solution {
public:
    bool contains(vector<int> &nums, int value) {
        for (int val : nums) {
            if (val == value) {
                return true;
            }
        }
        return false;
    }
};

    A few C++ details are worth knowing:

    • The parameter is a reference. vector<int> &nums means the method works on the caller's vector instead of copying it. Copying a large vector for every call would cost as much time as the search itself. Because the reference is not const, the method could change the vector, although this one does not. Writing const vector<int> &nums states that promise, but the lesson keeps the signature of the starter code.
    • The loop variable is a copy. In for (int val : nums), val is a copy of each element. For int that is as cheap as it gets. For bigger element types such as string, you would write const auto &val to avoid copying.
    • The empty vector is handled by the loop. If nums has no elements, the loop body never runs and the method returns false.
    • Returning a bool. true and false are keywords in lowercase. Printed with cout, they appear as 1 and 0 unless you add boolalpha.

    Complexity

    Time: O(n), where n is the number of elements. In the worst case the value is the last element or missing, and the loop makes n comparisons. In the best case the value is the first element and there is one comparison.

    Space: O(1). The method uses the loop variable and nothing else that grows with the input.

    The linear scan is the best you can do on an unsorted vector, because any element you skip might be the one you need. If the vector is sorted, binary search finds a value in O(log n), but sorting an unsorted vector first costs more than one scan.

    What C++ already provides

    This exercise asks you to write the loop, but in everyday code you would use the standard library. Searches like "c++ array contains" usually end at one of these:

    • std::find from <algorithm>: find(nums.begin(), nums.end(), value) != nums.end(). It returns an iterator to the first match, or end() if there is none. This works for vector, std::array and plain arrays (with pointers).
    • std::any_of when the test is more than equality, for example any_of(nums.begin(), nums.end(), [](int x) { return x < 0; }).
    • contains on sets and maps. std::set and std::unordered_set have a contains member since C++20, and count or find before that. If you test membership many times, put the values in an unordered_set once, and each lookup is O(1) on average.
    • std::ranges::contains searches any range, but it only arrived in C++23.

    Neither vector nor std::array has a contains member function, so nums.contains(value) does not compile.

    Plain C-style arrays, as in "c array contains", need one more thing: their length. An int array inside the function that declared it has a known size (sizeof(arr) / sizeof(arr[0])), but once it is passed to a function it becomes a pointer, and the same expression no longer gives the element count. Pass the length as a second parameter, and loop with an index from 0 to n - 1.

    Edge cases and common mistakes

    • Empty vector. The answer is always false, and the loop handles it without special code.
    • Duplicates. With nums = [3, 3, 3] and value = 3, the method returns true at the first element. It does not matter how many times the value occurs.
    • Negative numbers and zero. They compare like any other int. Searching for 0 in [-1, 2, -4, 0, 10] returns true.
    • Returning false too early. Putting return false inside the loop makes the method check only the first element.
    • Using = instead of ==. if (val = value) assigns instead of comparing, and the condition is true whenever value is not zero. Compilers usually warn about it.

    Testing

    • nums = [1, 2, 4, 5], value = 4 gives true.
    • nums = [-1, 2, -4, 0, 10], value = 7 gives false.
    • nums = [], value = 3 gives false.
    • nums = [3, 3, 3], value = 3 gives true.
    Keep going with C++About 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free