Linear Search

Linear Search Algorithm in C++ (Complete Implementation)

BeginnerTopic: Sorting & Searching Programs

C++ Linear Search Program

This program helps you to learn the fundamental structure and syntax of C++ programming.

#include <iostream>
using namespace std;

int linearSearch(int arr[], int n, int key) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == key) {
            return i;  // Return index if found
        }
    }
    return -1;  // Return -1 if not found
}

int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);
    int key;
    
    cout << "Array: ";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
    
    cout << "Enter element to search: ";
    cin >> key;
    
    int result = linearSearch(arr, n, key);
    
    if (result != -1) {
        cout << "Element found at index: " << result << endl;
    } else {
        cout << "Element not found in array" << endl;
    }
    
    return 0;
}

Output

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

Understanding Linear Search

This program teaches you how to implement the Linear Search algorithm in C++. Linear Search is the simplest searching algorithm that sequentially checks each element of the array from the beginning until it finds the target element or reaches the end. It works on both sorted and unsorted arrays, making it versatile but inefficient for large datasets.

---

1. What This Program Does

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.

---

2. Header File Used

This header provides:

•cout for displaying output

•cin for taking input from the user

---

#include <iostream>

3. 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

---

4. 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

}

            return 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

---

5. 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

---

6. 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

---

7. 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)

---

8. 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

---

9. Advantages and Disadvantages

Advantages

•Simple to understand and implement

•Works on unsorted arrays

•No preprocessing required

•Versatile - works on any data type

Disadvantages

•Slow for large arrays: O(n) time

•Inefficient compared to Binary Search for sorted arrays

•Must check every element in worst case

---

10. return 0;

This ends the program successfully.

---

Summary

•Linear Search sequentially checks each element until match found or array exhausted.

•Time complexity: O(n) worst/average, O(1) best case.

•Space complexity: O(1) - only uses constant extra space.

•Works on both sorted and unsorted arrays.

•Simple algorithm - easy to understand and implement.

•Returns index if found, -1 if not found.

•Best for small arrays or unsorted data.

•Understanding Linear Search is foundation for learning efficient search algorithms.

This program is fundamental for beginners learning searching algorithms, understanding sequential access, and preparing for more efficient algorithms like Binary Search in C++ programs.

Let us now understand every line and the components of the above program.

Note: To write and run C++ programs, you need to set up the local environment on your computer. Refer to the complete article Setting up C++ Development Environment. If you do not want to set up the local environment on your computer, you can also use online IDE to write and run your C++ programs.

Practical Learning Notes for Linear Search

This C++ program is part of the "Sorting & Searching Programs" topic and is designed to help you build real problem-solving confidence, not just memorize syntax. Start by understanding the goal of the program in plain language, then trace the logic line by line with a custom input of your own. Once you can predict the output before running the code, your understanding becomes much stronger.

A reliable practice pattern is to run the original version first, then modify only one condition or variable at a time. Observe how that single change affects control flow and output. This deliberate style helps you understand loops, conditions, and data movement much faster than copying full solutions repeatedly.

For interview preparation, explain this solution in three layers: the high-level approach, the step-by-step execution, and the time-space tradeoff. If you can teach these three layers clearly, you are ready to solve close variations of this problem under time pressure.

Binary Search (Iterative)

Counting Sort