Linear Search

1. Linear Search Algorithm
2. Linear Search Example
3. Linear Search Algorithm Implementation
4. Linear Search Algorithm Complexity

Linear search is the most simple searching algorithm. It is also called sequential search because, in this algorithm, we search for an element by traversing the whole array and comparing each element with the desired item to find a match. If the desired element is found, then the index or that element is returned; otherwise, we continue to search till we exhaust the array. We can also look for multiple occurrences of an item inside an array. It is mostly used to search items inside an unsorted array. It is not used practically because it is much slower than binary search.

Linear Search Algorithm

Let us assume that we have an unsorted array A[] containing n elements, and we want to find an element - X.

Linear Search Example

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

• Case 1: We want to look for X = 5.

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

• Case 2: We want to look for X = 1.

We traverse the array and reach index 4 to find a match and return that index. (Average Case)

• Case 3: We want to look for X = 9

We traverse the array but do not find a match when we reach the array’s last element. We return -1. (Worst Case)

Linear Search Algorithm Implementation

Linear Search Algorithm for 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] << " ";
    }
  }
}

Linear Search Algorithm Complexity

Time Complexity

• Average Case

The time complexity of the Linear Search Algorithm is O(n).

• Best Case

The best-case time complexity is O(1). It occurs when the element to be searched is the first element present inside the array.

• Worst-Case

The worst-case occurs when the element we are searching for is not present inside the array or is at the array’s last index. 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 stated as O(1) but can be more if multiple matching indexes are stored inside an array.