C++ Program for Linear Search with Example and Output

A C++ program for linear search uses a for loop to check each element in an array until it finds the target value or reaches the end; for example, for (int i = 0; i < n; i++) { if (arr[i] == target) return i; }.

Examples

InputArray: [5, 3, 8, 6, 2], Target: 8

OutputElement found at index 2

InputArray: [10, 20, 30, 40], Target: 25

OutputElement not found

InputArray: [], Target: 1

OutputElement not found

How to Think About It

To perform a linear search, start from the first element of the array and compare it with the target value. Move to the next element if it does not match. Continue this until you find the target or reach the end of the array.

Algorithm

1

Get the array and the target value from the user.

2

Start from the first element of the array.

3

Compare the current element with the target value.

4

If they match, return the current index.

5

If not, move to the next element and repeat until the end.

6

If the target is not found, return -1 to indicate failure.

Code

cpp

#include <iostream>
using namespace std;

int linearSearch(int arr[], int n, int target) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == target) {
            return i;
        }
    }
    return -1;
}

int main() {
    int arr[] = {5, 3, 8, 6, 2};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 8;
    int result = linearSearch(arr, n, target);
    if (result != -1) {
        cout << "Element found at index " << result << endl;
    } else {
        cout << "Element not found" << endl;
    }
    return 0;
}

Output

Element found at index 2

Dry Run

Let's trace the search for target 8 in the array [5, 3, 8, 6, 2].

1

Check index 0

arr[0] = 5, target = 8, not equal, continue

2

Check index 1

arr[1] = 3, target = 8, not equal, continue

3

Check index 2

arr[2] = 8, target = 8, equal, return index 2

Index	Array Value	Comparison Result
0	5	No match
1	3	No match
2	8	Match found

Why This Works

Step 1: Loop through array

The for loop goes through each element one by one to check for the target.

Step 2: Compare elements

Each element is compared with the target using == to find a match.

Step 3: Return index or -1

If a match is found, the index is returned; otherwise, -1 signals the target is not in the array.

Alternative Approaches

Using while loop

cpp

#include <iostream>
using namespace std;

int linearSearch(int arr[], int n, int target) {
    int i = 0;
    while (i < n) {
        if (arr[i] == target) return i;
        i++;
    }
    return -1;
}

int main() {
    int arr[] = {5, 3, 8, 6, 2};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 6;
    int result = linearSearch(arr, n, target);
    if (result != -1) cout << "Element found at index " << result << endl;
    else cout << "Element not found" << endl;
    return 0;
}

This uses a <code>while</code> loop instead of <code>for</code>, which some find easier to read for simple searches.

Using recursion

cpp

#include <iostream>
using namespace std;

int linearSearch(int arr[], int n, int target, int index = 0) {
    if (index == n) return -1;
    if (arr[index] == target) return index;
    return linearSearch(arr, n, target, index + 1);
}

int main() {
    int arr[] = {5, 3, 8, 6, 2};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 2;
    int result = linearSearch(arr, n, target);
    if (result != -1) cout << "Element found at index " << result << endl;
    else cout << "Element not found" << endl;
    return 0;
}

This recursive approach calls the function repeatedly, which is elegant but uses more memory.

Complexity: O(n) time, O(1) space

Time Complexity

Linear search checks each element once, so in the worst case it runs through all n elements, making it O(n).

Space Complexity

It uses only a few variables and no extra data structures, so space complexity is O(1).

Which Approach is Fastest?

All linear search methods have the same time complexity, but iterative versions use less memory than recursion.

Approach	Time	Space	Best For
For loop	O(n)	O(1)	Simple and efficient for small arrays
While loop	O(n)	O(1)	Alternative loop style, same efficiency
Recursion	O(n)	O(n)	Elegant but uses more memory