Linear Search
How linear search works and its time complexity.
Introduction
Given an array of numbers. We need to find the index of the number . That is, find such that . Alternatively, respond that such an index does not exist.
How linear search works and its time complexity.
Given an array of numbers. We need to find the index of the number . That is, find such that . Alternatively, respond that such an index does not exist.
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 since, in the worst case, it may check all numbers.
For implementation, both a for loop and a while loop can be used.
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
}
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;
}