Introduction

Given an array $a_1, a_2, \ldots, a_n$ of $n$ numbers. We need to find the index of the number $x$. That is, find $i \ (1 \leq i \leq n)$ such that $a_i=x$. Alternatively, respond that such an index does not exist.

Algorithm

To solve this problem, we can use linear search. Linear search is an algorithm that goes through the entire array and checks each element until it finds the desired element. This algorithm has a time complexity of $O(n)$ since, in the worst case, it may check all numbers.

For implementation, both a for loop and a while loop can be used.

For 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; // if doesn't exist
}

While Loop

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;
}