Implement Linear Search in Arrays
In this step, you'll learn how to implement a Linear Search algorithm in C++. Linear Search is a simple method of finding an element in an array by checking each element sequentially until the target is found or the end of the array is reached.
Open the WebIDE and create a new file called linear_search.cpp in the ~/project directory:
touch ~/project/linear_search.cpp
Add the following code to the linear_search.cpp file:
#include <iostream>
int linearSearch(int arr[], int size, int target) {
// Iterate through each element in the array
for (int i = 0; i < size; i++) {
// Check if current element matches the target
if (arr[i] == target) {
return i; // Return the index if found
}
}
return -1; // Return -1 if target is not found
}
int main() {
// Create an array of student scores
int scores[] = {85, 92, 78, 95, 88, 76, 90};
int size = sizeof(scores) / sizeof(scores[0]);
// Target score to search
int targetScore = 78;
// Perform linear search
int result = linearSearch(scores, size, targetScore);
// Display search results
if (result != -1) {
std::cout << "Target score " << targetScore
<< " found at index " << result << std::endl;
} else {
std::cout << "Target score " << targetScore
<< " not found in the array" << std::endl;
}
// Try another search
int missingScore = 100;
result = linearSearch(scores, size, missingScore);
if (result != -1) {
std::cout << "Score " << missingScore
<< " found at index " << result << std::endl;
} else {
std::cout << "Score " << missingScore
<< " not found in the array" << std::endl;
}
return 0;
}
Key Linear Search concepts:
- Checks each array element sequentially
- Returns the index of the target if found
- Returns -1 if target is not in the array
- Time complexity: O(n) - linear time
- Simple and works for unsorted arrays
Compile and run the program:
g++ linear_search.cpp -o linear_search
./linear_search
Example output:
Target score 78 found at index 2
Score 100 not found in the array
Important search notes:
- Linear Search is straightforward but inefficient for large arrays
- Suitable for small arrays or unsorted collections
- More efficient search algorithms exist for sorted arrays
