Linear Search

Check every item

Linear search starts at the beginning and checks each item until it finds the target or runs out.

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int linearSearch(const vector<string>& v, const string& target) {
    for (int i = 0; i < (int)v.size(); i++)
        if (v[i] == target) return i;
    return -1;
}

int main() {
    vector<string> books = {"Dune", "Emma", "Ulysses", "Hamlet"};
    cout << linearSearch(books, "Ulysses") << " " << linearSearch(books, "Matilda") << endl;
    return 0;
}

Output

2 -1

Think of it like this: Looking for your keys by checking every pocket, one after another.

std::find and std::count from <algorithm> are linear searches too.