Linear Search

Introduction

Suppose we are given an array

a_1, a_2, \ldots, a_n

and a value $x$ .

We need to find an index such that

i

a_i = x

or determine that such an index does not exist.

Algorithm

A simple way to solve this problem is linear search.

The idea is straightforward: we scan the array from left to right and compare each element with $x$ until we either find the required value or reach the end of the array.

In the worst case, we may need to check all elements, so the time complexity is:

O(n)

Linear search can be implemented using either a for loop or a while loop.

For Loop

While Loop

int Search(const vector<int>& a, int x) {
    for (size_t i = 0; i < a.size(); i++) {
        if (a[i] == x) {
            return i;
        }
    }
    return -1; // not found
}

int Search(const vector<int>& a, int x) {
    size_t i = 0;
    while (i < a.size() && a[i] != x) {
        i += 1;
    }
    if (i == a.size()) {
        return -1;
    }
    return i;
}