Things we will discuss here

  • Introduction
  • Linear Search Algorithm
  • Time and Space Complexity
  • C++ Implementation
  • Practice Problems

Introduction

Linear search is a Search Algorithm as the name suggests. It is used on a collection of items. It relies on the technique of traversing a list from start to end by exploring the properties of all the elements that are found on the way.

Linear Search Algorithm

  • Take a collection of elements and let k (be the value to be searched for).
  • Now traverse (go through all the elements) the collection and check whether that element is equal to k or not.
    • If equal then print “Found” and break the loop.
    • Else go till the last element and if not found then print “Not Found”.

Example: Taking an array of 9 elements and searching for 4 in it.

Time and Space Complexity

Time Complexity

  • In this, in the worst case, we will be going to all the elements.
  • Hence the complexity is O(n) where n-number of elements in a collection.

Space Complexity

  • Here we need to store all the n elements in an array before searching so the space complexity it O(n).

C++ Implementation

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

int main() {
    int n;  // Number of element
    cin >> n;

    vector<int> arr(n);  // Declaring array of size n.
    for (int i = 0; i < n; i++) cin >> arr[i];

    int k;  // Number to be searched for in the array.
    cin >> k;

    bool found = false;  // found = true if number is present in array.
    for (int i = 0; i < n; i++) {
        if (arr[i] == k) {
            cout << "Found\n";
            found = true;
            break;
        }
    }

    // if number is not present.
    if (!found) {
        cout << "Not Found\n";
    }

    return 0;
}

Input 1

5
1 2 3 4 5
4

Output 1

Found

Input 2

5
1 2 3 4 5
7

Output 2

Not Found

Practice Problems

If you have some content OR material related to this OR there is an error then do share them through the comment section for which we will be thankful to you.


Thank You for Reading

Leave a Reply