C++ Searching Algorithms

Searching algorithms are methods for finding whether a value exists in a collection, and often where it is located. In C++, searching is common with arrays, vectors, strings, lists, trees, and other data structures.

The right search algorithm depends on how the data is stored. Unsorted data usually needs a simple scan, while sorted data can often be searched much faster.

Linear Search

Linear search checks elements one at a time from the beginning until it finds the target or reaches the end. It works on both sorted and unsorted data.

Linear search is easy to write and useful for small collections. Its cost grows with the number of elements because, in the worst case, it may need to inspect every element.

#include <iostream>
#include <vector>

int linearSearch(const std::vector<int>& values, int target) {
    for (int i = 0; i < static_cast<int>(values.size()); i++) {
        if (values[i] == target) {
            return i;
        }
    }

    return -1;
}

int main(void) {
    std::vector<int> scores = {84, 91, 76, 100, 68};

    int firstIndex = linearSearch(scores, 100);
    int secondIndex = linearSearch(scores, 50);

    std::cout << "100 found at index: " << firstIndex << std::endl;
    std::cout << "50 found at index: " << secondIndex << std::endl;

    return 0;
}

Output:

100 found at index: 3
50 found at index: -1

How Linear Search Works

The function receives a vector by const reference so it can read the data without copying or modifying it. The loop compares each element with target. If a match is found, the function returns that index immediately.

If the loop finishes without finding a match, the function returns -1. That value is a common signal for not found when a function normally returns an index.

Binary Search

Binary search works only when the data is already sorted. Instead of checking every element, it checks the middle element and decides whether to continue in the left half or the right half.

Each comparison can remove about half of the remaining values from consideration. This makes binary search much faster than linear search for large sorted collections.

#include <iostream>
#include <vector>

int binarySearch(const std::vector<int>& values, int target) {
    int left = 0;
    int right = static_cast<int>(values.size()) - 1;

    while (left <= right) {
        int middle = left + (right - left) / 2;

        if (values[middle] == target) {
            return middle;
        }

        if (values[middle] < target) {
            left = middle + 1;
        } else {
            right = middle - 1;
        }
    }

    return -1;
}

int main(void) {
    std::vector<int> ids = {101, 104, 110, 115, 130, 142};

    std::cout << "115 found at index: " << binarySearch(ids, 115) << std::endl;
    std::cout << "120 found at index: " << binarySearch(ids, 120) << std::endl;

    return 0;
}

Output:

115 found at index: 3
120 found at index: -1

How Binary Search Works

The variables left and right mark the part of the vector that may still contain the target. The middle index is checked first.

If the middle value is too small, the target can only be to the right, so left moves past middle. If the middle value is too large, the target can only be to the left, so right moves before middle.

The loop stops when left moves past right. At that point there is no remaining range to search, so the function returns -1.

Linear Search vs Binary Search

Algorithm	Requires sorted data?	Basic idea	Typical use
Linear search	No	Check each element in order	Small or unsorted collections
Binary search	Yes	Repeatedly cut the search range in half	Large sorted vectors or arrays

Sorting just to use binary search is not always worth it for one lookup. But if you need to search the same data many times, keeping it sorted can be a good choice.

Standard Library Search Helpers

C++ also provides search algorithms in <algorithm>. Use std::find() for a simple linear search and std::binary_search() when the range is sorted and you only need a yes-or-no answer.

#include <algorithm>
#include <iostream>
#include <vector>

int main(void) {
    std::vector<int> numbers = {2, 4, 6, 8, 10};

    bool hasSix = std::find(numbers.begin(), numbers.end(), 6) != numbers.end();
    bool hasSeven = std::binary_search(numbers.begin(), numbers.end(), 7);

    std::cout << "Has 6: " << hasSix << std::endl;
    std::cout << "Has 7: " << hasSeven << std::endl;

    return 0;
}

Output:

Has 6: 1
Has 7: 0

Common Mistakes

• Do not use binary search on unsorted data.
• Remember that indexes start at 0.
• Check for a not-found result before using an index returned by a search function.
• Use library algorithms when they express the intent more clearly than hand-written loops.

Takeaway: linear search works anywhere, but binary search is much faster when the data is sorted.