JIYIK CN >

Linear search is the simplest search algorithm. It is also called sequential search because in this algorithm, we look for the matching element by going through the entire array and comparing each element with the required item. If the required element is found, then the index or the element is returned; otherwise, we continue searching until we exhaust the array. We can also look for multiple occurrences of an item in an array. It is mainly used to search for an item in an unsorted array. Since it is much slower than binary search, it is not used in practice.

Linear Search Algorithm

Suppose we have an unsorted array A[]containing nelements and we want to find an element - X.

• Use a for loop to iterate over all the elements in an array starting from the leftmost element and do the following.
  • If the value of A[i] matches X, return index i. (If there could be more than one element matching X, instead of returning index i, print all the indices or store all the indices in an array and return that array.)
  • Otherwise continue with the next element.
  • If you are at the last element of the array, exit the for loop.
• If none of the elements match, -1 is returned.

Linear Search Example

Suppose we have the array: (5, 3, 4, 2, 1, 6).

• Case 1: We are looking for X= 5.

The first element itself is a match and we return the index 0. (Best case)

• Case 2: We want to find X= 1.

We iterate over the array and reach the index 4, find a matching index and return that index. (Average case)

• Case 3: We are looking for X= 9.

We iterate over the array, but when we reach the last element of the array, no matching element is found. We return -1. (worst case)

Implementation of Linear Search Algorithm

Linear search algorithm for a single match

#include <iostream>
using namespace std;

int search(int arr[], int n, int x) {
    // Traverse the array sequentially
    for (int i = 0; i < n; i++) {
        if (arr[i] == x)
            return i;
    }
    return -1;
}

int main() {
    int n = 5;
    int arr[] = {2, 4, 0, 1, 9};
    int x = 1;
    int result = search(arr, n, x);
    if (result == -1) cout << "Element not found";
    else cout << "Element found at index: " << result;
}

Linear search algorithm for multiple matches

#include <bits/stdc++.h>
using namespace std;

vector<int> search(int arr[], int n, int x) {
    vector<int>ans;
    // Traverse the array sequentially
    for (int i = 0; i < n; i++) {
        if (arr[i] == x) {
            ans.push_back(i);
        }
    }
    return ans;
}

int main() {
    int n = 9;
    int arr[] = {2, 4, 0, 1, 9, 2, 1, 2, 1};
    int x = 1;
    vector<int> res = search(arr, n, x);
    if (res.empty()) {
        cout << "Element not found!!";
    }
    else {
        cout << "Element found at ";
        for (int i = 0; i < res.size(); i++) {
            cout << res[i] << " ";
        }
    }
}

Complexity of Linear Search Algorithm

Time Complexity

• Average situation

The time complexity of the linear search algorithm is O(n).

• Best Case

The best case time complexity is O(1). This occurs when the element being searched is the first element in the array.

• Worst case scenario

The worst case is when the element we are searching for is not in the array or is at the last index of the array. The worst case time complexity is O(n).

Space complexity

The space complexity of this algorithm depends on the number of matches and the implementation used. In general, the space complexity is O(1), but it can be higher if you store multiple match indices in an array.