Linear Search in C++

Linear Search Algorithm in C++ (Complete Implementation).

BeginnerSorting & Searching ProgramsExample 9 of 13

linear-search.cpp

1#include <iostream>
2using namespace std;
3
4int linearSearch(int arr[], int n, int key) {
5    for (int i = 0; i < n; i++) {
6        if (arr[i] == key) {
7            return i;  // Return index if found
8        }
9    }
10    return -1;  // Return -1 if not found
11}
12
13int main() {
14    int arr[] = {64, 34, 25, 12, 22, 11, 90};
15    int n = sizeof(arr) / sizeof(arr[0]);
16    int key;
17    
18    cout << "Array: ";
19    for (int i = 0; i < n; i++) {
20        cout << arr[i] << " ";
21    }
22    cout << endl;
23    
24    cout << "Enter element to search: ";
25    cin >> key;
26    
27    int result = linearSearch(arr, n, key);
28    
29    if (result != -1) {
30        cout << "Element found at index: " << result << endl;
31    } else {
32        cout << "Element not found in array" << endl;
33    }
34    
35    return 0;
36}

Output

Array: 64 34 25 12 22 11 90
Enter element to search: 25
Element found at index: 2

What's going on

The program searches for an element in an array using Linear Search. For example:

Array: [64, 34, 25, 12, 22, 11, 90]

Search for: 25

Result: Element found at index 2

Linear Search checks each element one by one until it finds a match or exhausts all elements.

Header File Used

This header provides:

cout for displaying output

cin for taking input from the user

1#include <iostream>

Understanding Linear Search

Algorithm Concept

Start from first element (index 0)

Compare each element with target

If match found, return index

If end reached, return -1 (not found)

Visual Example

Array: [64, 34, 25, 12, 22, 11, 90]

Search for: 25

Step 1: Check arr[0] = 64 → not 25, continue

Step 2: Check arr[1] = 34 → not 25, continue

Step 3: Check arr[2] = 25 → match! Return index 2

Function: linearSearch()

int linearSearch(int arr[], int n, int key) {

for (int i = 0; i < n; i++) {

if (arr[i] == key) {

}

return -1; // Return -1 if not found

}

1return i;  // Return index if found

How it works

Iterates through array from index 0 to n-1

Compares each element with key

Returns index if match found

Returns -1 if key not found

Step-by-Step Algorithm

For each element in array

Step 1: Check Current Element

Compare arr[i] with key

If equal: element found, return index i

If not equal: continue to next element

Step 2: Move to Next Element

Increment i

Repeat comparison

Step 3: End of Array

If i reaches n, all elements checked

Key not found, return -1

Example

(searching for 25):

i=0: arr[0]=64 ≠ 25 → continue

i=1: arr[1]=34 ≠ 25 → continue

i=2: arr[2]=25 = 25 → found! Return 2

Time and Space Complexity

Time Complexity

Best case: O(1) - element at first position

Worst case: O(n) - element at last position or not found

Average case: O(n) - element in middle on average

Space Complexity

: O(1)

Only uses constant extra space

No additional arrays or data structures needed

When to Use Linear Search

Best For

Small arrays

Unsorted arrays

When array is not frequently searched

Simple implementation needed

When data is not sorted

Not Recommended For

Large arrays (use Binary Search if sorted)

Frequent searches (sort first, then use Binary Search)

Performance-critical applications

When array is already sorted (Binary Search is better)

Important Considerations

Works on Any Array

Sorted arrays: works but inefficient

Unsorted arrays: only option (must sort first for Binary Search)

No preprocessing required

Return Value

Returns index if found (0 to n-1)

Returns -1 if not found

Check return value before using index

Comparison Count

Best case: 1 comparison (element at start)

Worst case: n comparisons (element at end or not found)

Average case: n/2 comparisons

return 0;

This ends the program successfully.

PreviousCounting Sort NextBinary Search (Iterative)